<!DOCTYPE HTML>
<html lang="en" >
    
    <head>
        
        <meta charset="UTF-8">
        <meta http-equiv="X-UA-Compatible" content="IE=edge" />
        <title>剑指offer25-43题 | python 数据结构与算法</title>
        <meta content="text/html; charset=utf-8" http-equiv="Content-Type">
        <meta name="description" content="">
        <meta name="generator" content="GitBook 2.6.7">
        
        
        <meta name="HandheldFriendly" content="true"/>
        <meta name="viewport" content="width=device-width, initial-scale=1, user-scalable=no">
        <meta name="apple-mobile-web-app-capable" content="yes">
        <meta name="apple-mobile-web-app-status-bar-style" content="black">
        <link rel="apple-touch-icon-precomposed" sizes="152x152" href="../gitbook/images/apple-touch-icon-precomposed-152.png">
        <link rel="shortcut icon" href="../gitbook/images/favicon.ico" type="image/x-icon">
        
    <link rel="stylesheet" href="../gitbook/style.css">
    
        
        <link rel="stylesheet" href="../gitbook/plugins/gitbook-plugin-highlight/website.css">
        
    
        
        <link rel="stylesheet" href="../gitbook/plugins/gitbook-plugin-search/search.css">
        
    
        
        <link rel="stylesheet" href="../gitbook/plugins/gitbook-plugin-fontsettings/website.css">
        
    
    

        
    
    
    <link rel="next" href="../树的实现/树的定义.html" />
    
    
    <link rel="prev" href="../剑指offer/剑指offer1-24题.html" />
    

        
    </head>
    <body>
        
        
    <div class="book"
        data-level="1.3"
        data-chapter-title="剑指offer25-43题"
        data-filepath="剑指offer/剑指offer25-43题.md"
        data-basepath=".."
        data-revision="Mon Jun 10 2019 17:10:15 GMT+0800 (中国标准时间)"
        data-innerlanguage="">
    

<div class="book-summary">
    <nav role="navigation">
        <ul class="summary">
            
            
            
            

            

            
    
        <li class="chapter " data-level="0" data-path="index.html">
            
                
                    <a href="../index.html">
                
                        <i class="fa fa-check"></i>
                        
                        python数据结构与算法
                    </a>
            
            
        </li>
    
        <li class="chapter " data-level="1" >
            
            <span><b>1.</b> 剑指offer</span>
            
            
            <ul class="articles">
                
    
        <li class="chapter " data-level="1.1" data-path="剑指offer/补码.html">
            
                
                    <a href="../剑指offer/补码.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>1.1.</b>
                        
                        补码
                    </a>
            
            
        </li>
    
        <li class="chapter " data-level="1.2" data-path="剑指offer/剑指offer1-24题.html">
            
                
                    <a href="../剑指offer/剑指offer1-24题.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>1.2.</b>
                        
                        剑指offer1-24题
                    </a>
            
            
        </li>
    
        <li class="chapter active" data-level="1.3" data-path="剑指offer/剑指offer25-43题.html">
            
                
                    <a href="../剑指offer/剑指offer25-43题.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>1.3.</b>
                        
                        剑指offer25-43题
                    </a>
            
            
        </li>
    

            </ul>
            
        </li>
    
        <li class="chapter " data-level="2" data-path="树的实现/树的定义.html">
            
                
                    <a href="../树的实现/树的定义.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>2.</b>
                        
                        各种树
                    </a>
            
            
            <ul class="articles">
                
    
        <li class="chapter " data-level="2.1" data-path="树的实现/B-树.html">
            
                
                    <a href="../树的实现/B-树.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>2.1.</b>
                        
                        B-树
                    </a>
            
            
        </li>
    
        <li class="chapter " data-level="2.2" data-path="树的实现/B+树.html">
            
                
                    <a href="../树的实现/B+树.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>2.2.</b>
                        
                        B+树
                    </a>
            
            
        </li>
    
        <li class="chapter " data-level="2.3" data-path="树的实现/红黑树.html">
            
                
                    <a href="../树的实现/红黑树.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>2.3.</b>
                        
                        红黑树
                    </a>
            
            
        </li>
    

            </ul>
            
        </li>
    
        <li class="chapter " data-level="3" >
            
            <span><b>3.</b> 六大排序</span>
            
            
            <ul class="articles">
                
    
        <li class="chapter " data-level="3.1" data-path="六大排序/六大基本排序.html">
            
                
                    <a href="../六大排序/六大基本排序.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>3.1.</b>
                        
                        六大基本排序
                    </a>
            
            
        </li>
    
        <li class="chapter " data-level="3.2" data-path="六大排序/快速排序.html">
            
                
                    <a href="../六大排序/快速排序.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>3.2.</b>
                        
                        快速排序
                    </a>
            
            
        </li>
    

            </ul>
            
        </li>
    
        <li class="chapter " data-level="4" >
            
            <span><b>4.</b> 算法的介绍</span>
            
            
            <ul class="articles">
                
    
        <li class="chapter " data-level="4.1" data-path="算法的介绍/字典序算法.html">
            
                
                    <a href="../算法的介绍/字典序算法.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>4.1.</b>
                        
                        字典序算法
                    </a>
            
            
        </li>
    
        <li class="chapter " data-level="4.2" data-path="算法的介绍/布隆算法.html">
            
                
                    <a href="../算法的介绍/布隆算法.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>4.2.</b>
                        
                        布隆算法
                    </a>
            
            
        </li>
    

            </ul>
            
        </li>
    


            
            <li class="divider"></li>
            <li>
                <a href="https://www.gitbook.com" target="blank" class="gitbook-link">
                    Published with GitBook
                </a>
            </li>
            
        </ul>
    </nav>
</div>

    <div class="book-body">
        <div class="body-inner">
            <div class="book-header" role="navigation">
    <!-- Actions Left -->
    

    <!-- Title -->
    <h1>
        <i class="fa fa-circle-o-notch fa-spin"></i>
        <a href="../" >python 数据结构与算法</a>
    </h1>
</div>

            <div class="page-wrapper" tabindex="-1" role="main">
                <div class="page-inner">
                
                
                    <section class="normal" id="section-">
                    
                        <p>&#x6811;&#x7684;&#x77E5;&#x8BC6;&#x70B9;&#xFF1A;</p>
<h5 id="&#x4EC0;&#x4E48;&#x53EB;&#x505A;&#x6811;&#xFF1F;">&#x4EC0;&#x4E48;&#x53EB;&#x505A;&#x6811;&#xFF1F;</h5>
<p><strong>&#x6811;&#x72B6;&#x56FE;</strong>&#x662F;&#x4E00;&#x79CD;<a href="https://baike.baidu.com/item/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/1450" target="_blank">&#x6570;&#x636E;&#x7ED3;&#x6784;</a>&#xFF0C;&#x5B83;&#x662F;&#x7531;n&#xFF08;n&gt;=0&#xFF09;&#x4E2A;&#x6709;&#x9650;&#x7ED3;&#x70B9;&#x7EC4;&#x6210;&#x4E00;&#x4E2A;&#x5177;&#x6709;&#x5C42;&#x6B21;&#x5173;&#x7CFB;&#x7684;<a href="https://baike.baidu.com/item/%E9%9B%86%E5%90%88" target="_blank">&#x96C6;&#x5408;</a>&#x3002;&#x628A;&#x5B83;&#x53EB;&#x505A;&#x201C;&#x6811;&#x201D;&#x662F;&#x56E0;&#x4E3A;&#x5B83;&#x770B;&#x8D77;&#x6765;&#x50CF;&#x4E00;&#x68F5;&#x5012;&#x6302;&#x7684;&#x6811;&#xFF0C;&#x4E5F;&#x5C31;&#x662F;&#x8BF4;&#x5B83;&#x662F;&#x6839;&#x671D;&#x4E0A;&#xFF0C;&#x800C;&#x53F6;&#x671D;&#x4E0B;&#x7684;&#x3002;&#x5B83;&#x5177;&#x6709;&#x4EE5;&#x4E0B;&#x7684;&#x7279;&#x70B9;&#xFF1A;</p>
<p>&#x6BCF;&#x4E2A;&#x7ED3;&#x70B9;&#x6709;&#x96F6;&#x4E2A;&#x6216;&#x591A;&#x4E2A;&#x5B50;&#x7ED3;&#x70B9;&#xFF1B;&#x6CA1;&#x6709;&#x7236;&#x7ED3;&#x70B9;&#x7684;&#x7ED3;&#x70B9;&#x79F0;&#x4E3A;&#x6839;&#x7ED3;&#x70B9;&#xFF1B;&#x6BCF;&#x4E00;&#x4E2A;&#x975E;&#x6839;&#x7ED3;&#x70B9;&#x6709;&#x4E14;&#x53EA;&#x6709;&#x4E00;&#x4E2A;&#x7236;&#x7ED3;&#x70B9;&#xFF1B;&#x9664;&#x4E86;&#x6839;&#x7ED3;&#x70B9;&#x5916;&#xFF0C;&#x6BCF;&#x4E2A;&#x5B50;&#x7ED3;&#x70B9;&#x53EF;&#x4EE5;&#x5206;&#x4E3A;&#x591A;&#x4E2A;&#x4E0D;&#x76F8;&#x4EA4;&#x7684;&#x5B50;&#x6811;&#xFF1B;</p>
<p>&#x53F6;&#x8282;&#x70B9;&#x6CA1;&#x6709;&#x5B50;&#x8282;&#x70B9;&#xFF0C;&#x6839;&#x8282;&#x70B9;&#x6CA1;&#x6709;&#x7236;&#x8282;&#x70B9;&#x3002;</p>
<h5 id="&#x4EC0;&#x4E48;&#x662F;&#x4E8C;&#x53C9;&#x6811;&#xFF1F;">&#x4EC0;&#x4E48;&#x662F;&#x4E8C;&#x53C9;&#x6811;&#xFF1F;</h5>
<p>&#x6BCF;&#x4E2A;&#x8282;&#x70B9;&#x6700;&#x591A;&#x542B;&#x6709;&#x4E24;&#x4E2A;&#x5B50;&#x6811;&#x7684;&#x6811;&#x79F0;&#x4E3A;&#x4E8C;&#x53C9;&#x6811;&#x3002;&#x4E0B;&#x56FE;&#x5C31;&#x662F;&#x4E00;&#x4E2A;&#x4E8C;&#x53C9;&#x6811;&#x3002;</p>
<p>&#x5728;&#x8BA1;&#x7B97;&#x673A;&#x79D1;&#x5B66;&#x4E2D;&#xFF0C;&#x4E8C;&#x53C9;&#x6811;&#x662F;&#x6BCF;&#x4E2A;&#x7ED3;&#x70B9;&#x6700;&#x591A;&#x6709;&#x4E24;&#x4E2A;&#x5B50;&#x6811;&#x7684;&#x6811;&#x7ED3;&#x6784;&#x3002;&#x901A;&#x5E38;&#x5B50;&#x6811;&#x88AB;&#x79F0;&#x4F5C;&#x201C;&#x5DE6;&#x5B50;&#x6811;&#x201D;&#xFF08;left subtree&#xFF09;&#x548C;&#x201C;&#x53F3;&#x5B50;&#x6811;&#x201D;&#xFF08;right subtree&#xFF09;&#x3002;&#x4E8C;&#x53C9;&#x6811;&#x5E38;&#x88AB;&#x7528;&#x4E8E;&#x5B9E;&#x73B0;&#x4E8C;&#x53C9;&#x67E5;&#x627E;&#x6811;&#x548C;&#x4E8C;&#x53C9;&#x5806;&#x3002;</p>
<p>&#x4E00;&#x68F5;&#x6DF1;&#x5EA6;&#x4E3A;k&#xFF0C;&#x4E14;&#x6709;2^k-1&#x4E2A;&#x8282;&#x70B9;&#x7684;&#x4E8C;&#x53C9;&#x6811;&#xFF0C;&#x79F0;&#x4E3A;&#x6EE1;&#x4E8C;&#x53C9;&#x6811;&#x3002;&#x8FD9;&#x79CD;&#x6811;&#x7684;&#x7279;&#x70B9;&#x662F;&#x6BCF;&#x4E00;&#x5C42;&#x4E0A;&#x7684;&#x8282;&#x70B9;&#x6570;&#x90FD;&#x662F;&#x6700;&#x5927;&#x8282;&#x70B9;&#x6570;&#x3002;&#x800C;&#x5728;&#x4E00;&#x68F5;&#x4E8C;&#x53C9;&#x6811;&#x4E2D;&#xFF0C;&#x9664;&#x6700;&#x540E;&#x4E00;&#x5C42;&#x5916;&#xFF0C;&#x82E5;&#x5176;&#x4F59;&#x5C42;&#x90FD;&#x662F;&#x6EE1;&#x7684;&#xFF0C;&#x5E76;&#x4E14;&#x6700;&#x540E;&#x4E00;&#x5C42;&#x6216;&#x8005;&#x662F;&#x6EE1;&#x7684;&#xFF0C;&#x6216;&#x8005;&#x662F;&#x5728;&#x53F3;&#x8FB9;&#x7F3A;&#x5C11;&#x8FDE;&#x7EED;&#x82E5;&#x5E72;&#x8282;&#x70B9;&#xFF0C;&#x5219;&#x6B64;&#x4E8C;&#x53C9;&#x6811;&#x4E3A;&#x5B8C;&#x5168;&#x4E8C;&#x53C9;&#x6811;&#x3002;&#x5177;&#x6709;n&#x4E2A;&#x8282;&#x70B9;&#x7684;&#x5B8C;&#x5168;&#x4E8C;&#x53C9;&#x6811;&#x7684;&#x6DF1;&#x5EA6;&#x4E3A;floor(log2n)+1&#x3002;&#x6DF1;&#x5EA6;&#x4E3A;k&#x7684;&#x5B8C;&#x5168;&#x4E8C;&#x53C9;&#x6811;&#xFF0C;&#x81F3;&#x5C11;&#x6709;2k-1&#x4E2A;&#x8282;&#x70B9;&#xFF0C;&#x81F3;&#x591A;&#x6709;2k-1&#x4E2A;&#x8282;&#x70B9;</p>
<p><img src="images/&#x4E8C;&#x53C9;&#x6811;.png" alt=""></p>
<h5 id="&#x4E8C;&#x53C9;&#x6811;&#x7684;&#x904D;&#x5386;&#xFF1A;">&#x4E8C;&#x53C9;&#x6811;&#x7684;&#x904D;&#x5386;&#xFF1A;</h5>
<p>&#x904D;&#x5386;&#x662F;&#x5BF9;&#x6811;&#x7684;&#x4E00;&#x79CD;&#x6700;&#x57FA;&#x672C;&#x7684;&#x8FD0;&#x7B97;&#xFF0C;&#x6240;&#x8C13;&#x904D;&#x5386;&#x4E8C;&#x53C9;&#x6811;&#xFF0C;&#x5C31;&#x662F;&#x6309;&#x4E00;&#x5B9A;&#x7684;&#x89C4;&#x5219;&#x548C;&#x987A;&#x5E8F;&#x8D70;&#x904D;&#x4E8C;&#x53C9;&#x6811;&#x7684;&#x6240;&#x6709;&#x7ED3;&#x70B9;&#xFF0C;&#x4F7F;&#x6BCF;&#x4E00;&#x4E2A;&#x7ED3;&#x70B9;&#x90FD;&#x88AB;&#x8BBF;&#x95EE;&#x4E00;&#x6B21;&#xFF0C;&#x800C;&#x4E14;&#x53EA;&#x88AB;&#x8BBF;&#x95EE;&#x4E00;&#x6B21;&#x3002;&#x7531;&#x4E8E;&#x4E8C;&#x53C9;&#x6811;&#x662F;&#x975E;&#x7EBF;&#x6027;&#x7ED3;&#x6784;&#xFF0C;&#x56E0;&#x6B64;&#xFF0C;<a href="https://baike.baidu.com/item/%E6%A0%91%E7%9A%84%E9%81%8D%E5%8E%86" target="_blank">&#x6811;&#x7684;&#x904D;&#x5386;</a>&#x5B9E;&#x8D28;&#x4E0A;&#x662F;&#x5C06;&#x4E8C;&#x53C9;&#x6811;&#x7684;&#x5404;&#x4E2A;&#x7ED3;&#x70B9;&#x8F6C;&#x6362;&#x6210;&#x4E3A;&#x4E00;&#x4E2A;&#x7EBF;&#x6027;&#x5E8F;&#x5217;&#x6765;&#x8868;&#x793A;&#x3002;</p>
<p>&#x8BBE;L&#x3001;D&#x3001;R&#x5206;&#x522B;&#x8868;&#x793A;&#x904D;&#x5386;&#x5DE6;&#x5B50;&#x6811;&#x3001;&#x8BBF;&#x95EE;&#x6839;&#x7ED3;&#x70B9;&#x548C;&#x904D;&#x5386;&#x53F3;&#x5B50;&#x6811;&#xFF0C; &#x5219;&#x5BF9;&#x4E00;&#x68F5;&#x4E8C;&#x53C9;&#x6811;&#x7684;&#x904D;&#x5386;&#x6709;&#x4E09;&#x79CD;&#x60C5;&#x51B5;&#xFF1A;DLR&#xFF08;&#x79F0;&#x4E3A;&#x5148;&#x6839;&#x6B21;&#x5E8F;&#x904D;&#x5386;&#xFF09;&#xFF0C;LDR&#xFF08;&#x79F0;&#x4E3A;&#x4E2D;&#x6839;&#x6B21;&#x5E8F;&#x904D;&#x5386;&#xFF09;&#xFF0C;LRD &#xFF08;&#x79F0;&#x4E3A;&#x540E;&#x6839;&#x6B21;&#x5E8F;&#x904D;&#x5386;&#xFF09;&#x3002;</p>
<pre><code class="lang-python"><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">treeNode</span><span class="hljs-params">(object)</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">__init__</span><span class="hljs-params">(self,x)</span>:</span>
        self.val = x
        self.left = <span class="hljs-keyword">None</span>
        self.right = <span class="hljs-keyword">None</span>

<span class="hljs-comment">#1. &#x6DF1;&#x5EA6;&#x4F18;&#x5148;</span>
<span class="hljs-comment">#2. &#x5E7F;&#x5EA6;&#x4F18;&#x5148;</span>
<span class="hljs-comment">#&#x5BF9;&#x4E8E;&#x6DF1;&#x5EA6;&#x4F18;&#x5148;&#x6765;&#x8BF4;&#xFF1A;</span>
<span class="hljs-string">&quot;&quot;&quot;

1 &#x5148;&#x5E8F;&#x904D;&#x5386;  &#x5148;&#x6253;&#x5370;&#x6839; 1,2,4,5,3,6,8,7
2 &#x4E2D;&#x5E8F;&#x904D;&#x5386;  &#x5148;&#x6253;&#x5370;&#x5DE6;&#x4FA7;&#x7684;&#x53F6;&#x5B50;&#x8282;&#x70B9; 4&#xFF0C;&#x518D;&#x8F93;&#x51FA; &#x4E2D;&#x8282;&#x70B9;  2 &#xFF1B;  4 2 5 1 6 8 3 7 
3 &#x5148;&#x5E8F;&#x904D;&#x5386;  &#x8F93;&#x51FA;&#x987A;&#x5E8F;  4 5 2 8 6 7 3 1

&#x6CE8;&#x610F;&#xFF1A;  &#x5148;&#x5E8F;   &#x4E2D;&#x5E8F; &#x540E;&#x5E8F;  &#x90FD;&#x662F;&#x5BF9;&#x5E94;&#x4E8E;&#x6839;&#x8282;&#x70B9;&#x6765;&#x8BF4;&#x7684;&#xFF0C;&#x5DE6;&#x53F3;&#x8282;&#x70B9;&#x90FD;&#x662F;&#x5148;&#x5DE6;&#x540E;&#x53F3;

&quot;&quot;&quot;</span>
<span class="hljs-comment">#&#x9012;&#x5F52;</span>
<span class="hljs-comment">#&#x524D;&#x5E8F;&#x904D;&#x5386;</span>
<span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">preOrderRecusive</span><span class="hljs-params">(root)</span>:</span>
    <span class="hljs-keyword">if</span> root == <span class="hljs-keyword">None</span>:
        <span class="hljs-keyword">return</span> <span class="hljs-keyword">None</span>

    print(root.val)
    preOrderRecusive(root.left)
    preOrderRecusive(root.right)
<span class="hljs-comment">#&#x4E2D;&#x5E8F;&#x904D;&#x5386;</span>
<span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">midOrderRecusive</span><span class="hljs-params">(root)</span>:</span>
    <span class="hljs-keyword">if</span> root == <span class="hljs-keyword">None</span>:
        <span class="hljs-keyword">return</span> <span class="hljs-keyword">None</span>
    midOrderRecusive(root.left)
    print(root.val)
    midOrderRecusive(root.right)

<span class="hljs-comment">#&#x540E;&#x5E8F;&#x904D;&#x5386;</span>
<span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">laterOrderRecusive</span><span class="hljs-params">(root)</span>:</span>
    <span class="hljs-keyword">if</span> root == <span class="hljs-keyword">None</span>:
        <span class="hljs-keyword">return</span> <span class="hljs-keyword">None</span>
    laterOrderRecusive(root.left)
    laterOrderRecusive(root.right)
    print(root.val)

<span class="hljs-comment">#&#x975E;&#x9012;&#x5F52;&#x7684;&#x5F62;&#x5F0F; &#x53BB;&#x904D;&#x5386;&#x6570;</span>
<span class="hljs-comment">#&#x9012;&#x5F52;&#x548C;&#x5FAA;&#x73AF;&#x662F;&#x53EF;&#x4EE5;&#x4E92;&#x76F8;&#x8F6C;&#x6362;&#x7684;</span>

<span class="hljs-string">&quot;&quot;&quot;

1 &#x5148;&#x6839;&#x904D;&#x5386; &#x5148;&#x8BBF;&#x95EE;&#x6839;&#x8282;&#x70B9;&#xFF0C;&#x518D;&#x8BBF;&#x95EE;&#x5DE6;&#x5B50;&#x8282;&#x70B9;&#xFF0C;&#x6700;&#x540E;&#x8BBF;&#x95EE;&#x53F3;&#x5B50;&#x8282;&#x70B9;
2 &#x4E2D;&#x6839;&#x904D;&#x5386; &#x5148;&#x8BBF;&#x95EE;&#x5DE6;&#x5B50;&#x8282;&#x70B9;&#xFF0C;&#x518D;&#x8BBF;&#x95EE;&#x6839;&#x8282;&#x70B9;&#xFF0C;&#x6700;&#x540E;&#x8BBF;&#x95EE;&#x53F3;&#x5B50;&#x8282;&#x70B9;
3 &#x540E;&#x8DDF;&#x904D;&#x5386; &#x5148;&#x8BBF;&#x95EE;&#x5DE6;&#x5B50;&#x8282;&#x70B9;&#xFF0C;&#x518D;&#x8BBF;&#x95EE;&#x53F3;&#x5B50;&#x8282;&#x70B9;&#xFF0C;&#x6700;&#x540E;&#x8BBF;&#x95EE;&#x6839;&#x8282;&#x70B9;&#x3002;

&quot;&quot;&quot;</span>
<span class="hljs-comment">#&#x975E;&#x9012;&#x5F52;&#x7684;&#x524D;&#x5E8F;&#x904D;&#x5386;</span>
<span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">preOrder</span><span class="hljs-params">(root)</span>:</span>
    <span class="hljs-keyword">if</span> root == <span class="hljs-keyword">None</span>:
        <span class="hljs-keyword">return</span> <span class="hljs-keyword">None</span>
    stack = []
    tmpNode = root
    <span class="hljs-keyword">while</span> tmpNode <span class="hljs-keyword">or</span> stack :
        <span class="hljs-keyword">while</span> tmpNode:
            print(tmpNode.val)
            stack.append(tmpNode)
            tmpNode = tmpNode.left
        node  = stack.pop()
        tmpNode = node.right
<span class="hljs-comment">#&#x975E;&#x9012;&#x5F52;&#x7684;&#x4E2D;&#x5E8F;&#x6392;&#x5E8F;</span>
<span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">midOrder</span><span class="hljs-params">(root)</span>:</span>
    <span class="hljs-keyword">if</span> root == <span class="hljs-keyword">None</span>:
        <span class="hljs-keyword">return</span> <span class="hljs-keyword">None</span>
    stack = []
    tmpNode = root
    <span class="hljs-keyword">while</span> tmpNode <span class="hljs-keyword">or</span> stack :
        <span class="hljs-keyword">while</span> tmpNode:
            stack.append(tmpNode)
            tmpNode = tmpNode.left
        node  = stack.pop()
        print(node.val)
        tmpNode = node.right
<span class="hljs-comment">#&#x975E;&#x9012;&#x5F52;&#x7684;&#x540E;&#x5E8F;&#x904D;&#x5386;</span>
<span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">laterOrder</span><span class="hljs-params">(root)</span>:</span>
    <span class="hljs-keyword">if</span> root == <span class="hljs-keyword">None</span>:
        <span class="hljs-keyword">return</span> <span class="hljs-keyword">None</span>
    stack = []
    tmpNode = root
    <span class="hljs-keyword">while</span> tmpNode <span class="hljs-keyword">or</span> stack :
        <span class="hljs-keyword">while</span> tmpNode:
            stack.append(tmpNode)
            tmpNode = tmpNode.left
        node = stack[-<span class="hljs-number">1</span>]
        tmpNode = node.right
        <span class="hljs-keyword">if</span> node.right == <span class="hljs-keyword">None</span>:
            node = stack.pop()
            print(node.val)
            <span class="hljs-keyword">while</span> stack <span class="hljs-keyword">and</span> node == stack[-<span class="hljs-number">1</span>].right:
                node =  stack.pop()
                print(node.val)
</code></pre>
<h2 id="25&#x91CD;&#x5EFA;&#x4E8C;&#x53C9;&#x6811;">25.&#x91CD;&#x5EFA;&#x4E8C;&#x53C9;&#x6811;</h2>
<p><strong>&#x8F93;&#x5165;&#x67D0;&#x4E8C;&#x53C9;&#x6811;&#x7684;&#x524D;&#x5E8F;&#x904D;&#x5386;&#x548C;&#x4E2D;&#x5E8F;&#x904D;&#x5386;&#x7684;&#x7ED3;&#x679C;&#xFF0C;&#x8BF7;&#x91CD;&#x5EFA;&#x51FA;&#x8BE5;&#x4E8C;&#x53C9;&#x6811;&#x3002;&#x5047;&#x8BBE;&#x8F93;&#x5165;&#x7684;&#x524D;&#x5E8F;&#x904D;&#x5386;&#x548C;&#x4E2D;&#x5E8F;&#x904D;&#x5386;&#x7684;&#x7ED3;&#x679C;&#x4E2D;&#x90FD;&#x4E0D;&#x542B;&#x91CD;&#x590D;&#x7684;&#x6570;&#x5B57;&#x3002;&#x4F8B;&#x5982;&#x8F93;&#x5165;&#x524D;&#x5E8F;&#x904D;&#x5386;&#x5E8F;&#x5217;{1,2,4,7,3,5,6,8}&#x548C;&#x4E2D;&#x5E8F;&#x904D;&#x5386;&#x5E8F;&#x5217;{4,7,2,1,5,3,8,6}&#xFF0C;&#x5219;&#x91CD;&#x5EFA;&#x4E8C;&#x53C9;&#x6811;&#x5E76;&#x8FD4;&#x56DE;&#x3002;</strong></p>
<pre><code class="lang-python"><span class="hljs-comment"># -*- coding:utf-8 -*-</span>
<span class="hljs-comment"># class TreeNode:</span>
<span class="hljs-comment">#     def __init__(self, x):</span>
<span class="hljs-comment">#         self.val = x</span>
<span class="hljs-comment">#         self.left = None</span>
<span class="hljs-comment">#         self.right = None</span>
<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-comment"># &#x8FD4;&#x56DE;&#x6784;&#x9020;&#x7684;TreeNode&#x6839;&#x8282;&#x70B9;</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">reConstructBinaryTree</span><span class="hljs-params">(self, pre, tin)</span>:</span>
        <span class="hljs-comment"># write code here</span>
        <span class="hljs-comment">#&#x5224;&#x65AD; &#x5982;&#x679C; &#x662F;&#x524D;&#x5E8F; &#x6216;&#x8005;&#x540E;&#x5E8F; &#x904D;&#x5386;&#x7ED3;&#x679C; &#x6709;&#x4E3A;&#x7A7A;&#x7684;&#x8BDD;&#xFF0C;&#x90A3;&#x4E48;&#x5C31;&#x8FD4;&#x56DE;none</span>
        <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> pre <span class="hljs-keyword">or</span> <span class="hljs-keyword">not</span> tin:
            <span class="hljs-keyword">return</span> <span class="hljs-keyword">None</span>
        <span class="hljs-comment">#&#x5982;&#x679C;&#x4E24;&#x4E2A;&#x904D;&#x5386;&#x7684;&#x957F;&#x5EA6;&#x4E0D;&#x4E00;&#x6837;&#xFF0C;&#x90A3;&#x4E48;&#x4E5F;&#x5C31;&#x8FD4;&#x56DE;&#x4E00;&#x4E2A;None</span>
        <span class="hljs-keyword">if</span> len(pre) != len(tin):
            <span class="hljs-keyword">return</span> <span class="hljs-keyword">None</span>
        <span class="hljs-comment">#&#x524D;&#x5E8F;&#x904D;&#x5386;&#x4E2D; &#x7B2C;&#x4E00;&#x4E2A;&#x6570; &#x5C31;&#x662F;&#x6839;&#x8282;&#x70B9;</span>
        <span class="hljs-comment"># &#x53D6;&#x51FA;pre &#x7684;&#x7B2C;&#x4E00;&#x4E2A;&#x503C;  &#x5C31;&#x662F;&#x6839;&#x8282;&#x70B9;</span>
        root = pre[<span class="hljs-number">0</span>]
        <span class="hljs-comment">#&#x91CD;&#x5EFA;&#x4E8C;&#x53C9;&#x6811;&#x7684; &#x6839;&#x8282;&#x70B9; </span>
        rootNode = TreeNode(root)
        <span class="hljs-comment"># &#x627E;&#x5230;&#x5728; tin  &#x4E2D;&#x5E8F;&#x904D;&#x5386;&#x4E2D;&#x7684;&#x6839;&#x8282;&#x70B9; &#x6240;&#x5728;&#x7684;&#x7D22;&#x5F15;&#x4F4D;&#x7F6E;</span>
        pos = tin.index(root)
        <span class="hljs-comment"># &#x4E2D;&#x5E8F;&#x904D;&#x5386;&#x7684; &#x5217;&#x8868;&#x7684;&#x5DE6;&#x53F3;&#x8282;&#x70B9; &#x5206;&#x5F00; &#x5207;&#x7247; &#x6210;&#x4E24;&#x4E2A;&#x5217;&#x8868;</span>
        <span class="hljs-comment">#&#x4E2D;&#x5E8F;&#x904D;&#x5386; &#x4E2D;&#x5E8F;&#x7684; &#x6839;&#x8282;&#x70B9; &#x7684; &#x6240;&#x5728;&#x4F4D;&#x7F6E; &#x7684; &#x5DE6;&#x8FB9;&#x90E8;&#x5206; &#x90FD;&#x662F;&#x6839;&#x8282;&#x70B9;&#x7684;&#x5DE6;&#x5B50;&#x6811;&#x4E0A;&#x7684;&#xFF0C;&#x53F3;&#x8FB9;&#x90FD;&#x662F;&#x6839;&#x8282;&#x70B9;&#x7684;&#x53F3;&#x5B50;&#x6811;&#x4E0A;&#x7684;</span>
        tinLeft = tin[<span class="hljs-number">0</span>:pos]
        tinRight = tin[pos + <span class="hljs-number">1</span>:]
        <span class="hljs-comment"># &#x524D;&#x5E8F;&#x904D;&#x5386;&#x7684; &#x5217;&#x8868;&#x7684;&#x5DE6;&#x53F3;&#x8282;&#x70B9; &#x5206;&#x5F00; &#x5207;&#x7247; &#x6210;&#x4E24;&#x4E2A;&#x5217;&#x8868;</span>
        <span class="hljs-comment">#&#x90A3;&#x5BF9;&#x4E8E;&#x524D;&#x5E8F;&#x904D;&#x5386;&#x6765;&#x8BF4;&#xFF0C; &#x5148;&#x8BBF;&#x95EE;&#x6839;&#x8282;&#x70B9;&#xFF0C;&#x518D;&#x8BBF;&#x95EE;&#x5DE6;&#x5B50;&#x8282;&#x70B9;&#xFF0C;&#x6700;&#x540E;&#x8BBF;&#x95EE;&#x53F3;&#x5B50;&#x8282;&#x70B9;</span>
        <span class="hljs-comment">#&#x90A3;&#x4E48;&#x524D;&#x5E8F;&#x904D;&#x5386;&#x7684;&#x5DE6;&#x5B50;&#x6811;&#x7684;&#x7ED3;&#x70B9; &#x5C31;&#x662F;&#x6839;&#x8282;&#x70B9;&#x7684;&#x4E0B;&#x4E00;&#x4E2A;&#x7ED3;&#x70B9;&#x5230; &#x524D;&#x5E8F;&#x904D;&#x5386;&#x7684;&#x975E;&#x6839;&#x8282;&#x70B9;&#xFF0C;&#x975E;&#x53F6;&#x5B50;&#x8282;&#x70B9;&#x7684; &#x7ED3;&#x70B9;&#x7684;&#x7D22;&#x5F15;&#x4F4D;&#x7F6E;&#xFF0C;&#x5C31;&#x662F;&#x8FD9;&#x4E2A;&#x5B50;&#x4E8C;&#x53C9;&#x6811;&#x7684;&#x5DE6;&#x5B50;&#x6811;&#x7684;&#x7ED3;&#x70B9;</span>
        preLeft = pre[<span class="hljs-number">1</span>:pos + <span class="hljs-number">1</span>]
        <span class="hljs-comment">#&#x90A3; &#x975E;&#x6839;&#x8282;&#x70B9;&#xFF0C;&#x975E;&#x53F6;&#x5B50;&#x8282;&#x70B9;&#x7684; &#x7ED3;&#x70B9;&#x7684;&#x7D22;&#x5F15;&#x4F4D;&#x7F6E;&#x7684;&#x4E0B;&#x4E00;&#x4E2A;&#x5F00;&#x59CB; &#x4E00;&#x76F4;&#x5230;&#x7ED3;&#x5C3E;&#xFF0C;&#x90FD;&#x662F;&#x8FD9;&#x4E2A;&#x7ED3;&#x70B9;&#x7684;&#x53F3;&#x5B50;&#x6811;&#x7684;&#x7ED3;&#x70B9;</span>
        preRight = pre[pos + <span class="hljs-number">1</span>:]
        <span class="hljs-comment">#&#x9012;&#x5F52;&#x91CD;&#x5EFA;&#x6839;&#x8282;&#x70B9;&#x7684;&#x5DE6;&#x8282;&#x70B9;&#xFF0C;&#x4E5F;&#x5C31;&#x662F; &#x6BCF;&#x4E2A; &#x975E;&#x6839;&#x8282;&#x70B9; &#x975E;&#x53F6;&#x5B50;&#x8282;&#x70B9;&#x90FD;&#x662F;&#x4E00;&#x4E2A;&#x6839;&#x8282;&#x70B9;&#x7684;&#x5B58;&#x5728;&#xFF0C;&#x90A3;&#x4E48;&#x8FD9;&#x4E2A;&#x65F6;&#x5019;&#x5C31;&#x662F;&#x9012;&#x5F52;&#x6765;&#x91CD;&#x5EFA;&#x8FD9;&#x4E2A; &#x4E8C;&#x53C9;&#x6811;&#x3002;</span>
        leftNode = self.reConstructBinaryTree(preLeft, tinLeft)
        rightNode = self.reConstructBinaryTree(preRight, tinRight)
        <span class="hljs-comment">#&#x6839;&#x8282;&#x70B9;&#x7684; &#x5DE6;&#x8282;&#x70B9; &#x7B49;&#x4E8E; &#x6211;&#x4EEC;&#x8981; &#x9012;&#x5F52; &#x7684; &#x5DE6;&#x8282;&#x70B9;&#xFF08;&#x4E00;&#x4E2A;&#x65B0;&#x7684;&#x6839;&#x8282;&#x70B9;&#xFF09;</span>
        rootNode.left = leftNode
        <span class="hljs-comment">#&#x6839;&#x8282;&#x70B9;&#x7684; &#x53F3;&#x8282;&#x70B9; &#x7B49;&#x4E8E; &#x6211;&#x4EEC;&#x8981; &#x9012;&#x5F52; &#x7684; &#x53F3;&#x8282;&#x70B9;&#xFF08;&#x4E00;&#x4E2A;&#x65B0;&#x7684;&#x6839;&#x8282;&#x70B9;&#xFF09;</span>
        rootNode.right = rightNode
        <span class="hljs-keyword">return</span> rootNode
</code></pre>
<hr>
<h2 id="26&#x6811;&#x7684;&#x5B50;&#x7ED3;&#x6784;">26.&#x6811;&#x7684;&#x5B50;&#x7ED3;&#x6784;</h2>
<p><strong>&#x8F93;&#x5165;&#x4E24;&#x68F5;&#x4E8C;&#x53C9;&#x6811;A&#xFF0C;B&#xFF0C;&#x5224;&#x65AD;B&#x662F;&#x4E0D;&#x662F;A&#x7684;&#x5B50;&#x7ED3;&#x6784;&#x3002;&#xFF08;ps&#xFF1A;&#x6211;&#x4EEC;&#x7EA6;&#x5B9A;&#x7A7A;&#x6811;&#x4E0D;&#x662F;&#x4EFB;&#x610F;&#x4E00;&#x4E2A;&#x6811;&#x7684;&#x5B50;&#x7ED3;&#x6784;&#xFF09;</strong></p>
<p>&#x5BF9;&#x4E8E;Python&#x8FD9;&#x9053;&#x9898;&#xFF0C;&#x6709;&#x4E9B;&#x5730;&#x65B9;&#x9700;&#x8981;&#x4ED4;&#x7EC6;&#x8003;&#x8651;&#x7684;&#x3002;</p>
<p>&#x5148;&#x8BF4;&#x4E0B;&#x7B97;&#x6CD5;&#x5B9E;&#x73B0;&#x601D;&#x8DEF;&#xFF1A;&#x5BF9;&#x4E8E;&#x4E24;&#x68F5;&#x4E8C;&#x53C9;&#x6811;&#x6765;&#x8BF4;&#xFF0C;&#x8981;&#x5224;&#x65AD;B&#x662F;&#x4E0D;&#x662F;A&#x7684;&#x5B50;&#x7ED3;&#x6784;&#xFF0C;&#x9996;&#x5148;&#x7B2C;&#x4E00;&#x6B65;&#x5728;&#x6811;A&#x4E2D;&#x67E5;&#x627E;&#x4E0E;B&#x6839;&#x8282;&#x70B9;&#x7684;&#x503C;&#x4E00;&#x6837;&#x7684;&#x8282;&#x70B9;&#x3002;</p>
<p>&#x901A;&#x5E38;&#x5BF9;&#x4E8E;&#x67E5;&#x627E;&#x6811;&#x4E2D;&#x67D0;&#x4E00;&#x4E2A;&#x8282;&#x70B9;&#xFF0C;&#x6211;&#x4EEC;&#x90FD;&#x662F;&#x91C7;&#x7528;&#x9012;&#x5F52;&#x7684;&#x65B9;&#x6CD5;&#x6765;&#x904D;&#x5386;&#x6574;&#x68F5;&#x6811;&#x3002;</p>
<p>&#x7B2C;&#x4E8C;&#x6B65;&#x5C31;&#x662F;&#x5224;&#x65AD;&#x6811;A&#x4E2D;&#x4EE5;R&#x4E3A;&#x6839;&#x8282;&#x70B9;&#x7684;&#x5B50;&#x6811;&#x662F;&#x4E0D;&#x662F;&#x548C;&#x6811;B&#x5177;&#x6709;&#x76F8;&#x540C;&#x7684;&#x7ED3;&#x6784;&#x3002;</p>
<p>&#x8FD9;&#x91CC;&#x540C;&#x6837;&#x5229;&#x7528;&#x5230;&#x4E86;&#x9012;&#x5F52;&#x7684;&#x65B9;&#x6CD5;&#xFF0C;&#x5982;&#x679C;&#x8282;&#x70B9;R&#x7684;&#x503C;&#x548C;&#x6811;&#x7684;&#x6839;&#x8282;&#x70B9;&#x4E0D;&#x76F8;&#x540C;&#xFF0C;&#x5219;&#x4EE5;R&#x4E3A;&#x6839;&#x8282;&#x70B9;&#x7684;&#x5B50;&#x6811;&#x548C;&#x6811;B&#x80AF;&#x5B9A;&#x4E0D;&#x5177;&#x6709;&#x76F8;&#x540C;&#x7684;&#x8282;&#x70B9;&#xFF1B;</p>
<p>&#x5982;&#x679C;&#x5B83;&#x4EEC;&#x503C;&#x662F;&#x76F8;&#x540C;&#x7684;&#xFF0C;&#x5219;&#x9012;&#x5F52;&#x7684;&#x5224;&#x65AD;&#x5404;&#x81EA;&#x7684;&#x5DE6;&#x53F3;&#x8282;&#x70B9;&#x7684;&#x503C;&#x662F;&#x4E0D;&#x662F;&#x76F8;&#x540C;&#x3002;</p>
<p>&#x9012;&#x5F52;&#x7684;&#x7EC8;&#x6B62;&#x6761;&#x4EF6;&#x662F;&#x6211;&#x4EEC;&#x8FBE;&#x5230;&#x4E86;&#x6811;A&#x6216;&#x8005;&#x6811;B&#x7684;&#x53F6;&#x8282;&#x70B9;&#x3002;</p>
<p>&#x6709;&#x5730;&#x65B9;&#x8981;&#x91CD;&#x70B9;&#x6CE8;&#x610F;&#xFF0C;DoesTree1haveTree2()&#x51FD;&#x6570;&#x4E2D;&#x7684;&#x4E24;&#x4E2A; if &#x5224;&#x65AD;&#x8BED;&#x53E5; &#x4E0D;&#x80FD;&#x98A0;&#x5012;&#x987A;&#x5E8F; &#x3002;
&#x56E0;&#x4E3A;&#x5982;&#x679C;&#x98A0;&#x5012;&#x4E86;&#x987A;&#x5E8F;&#xFF0C;&#x4F1A;&#x5148;&#x5224;&#x65AD;pRoot1 &#x662F;&#x5426;&#x4E3A;None, &#x5176;&#x5B9E;&#x8FD9;&#x4E2A;&#x65F6;&#x5019;&#xFF0C;pRoot1 &#x7684;&#x8282;&#x70B9;&#x5DF2;&#x7ECF;&#x904D;&#x5386;&#x5B8C;&#x6210;&#x786E;&#x8BA4;&#x76F8;&#x7B49;&#x4E86;&#xFF0C;&#x4F46;&#x662F;&#x8FD9;&#x4E2A;&#x65F6;&#x5019;&#x4F1A;&#x8FD4;&#x56DE; False&#xFF0C;&#x5224;&#x65AD;&#x9519;&#x8BEF;&#x3002;</p>
<p>&#x6709;&#x540C;&#x5B66;&#x4E0D;&#x76F8;&#x4FE1;&#x7684;&#xFF0C;&#x53EF;&#x4EE5;&#x53BB;&#x8BD5;&#x8BD5;&#x6362;&#x4E2A;&#x987A;&#x5E8F;&#xFF0C;&#x80AF;&#x5B9A;&#x4E0D;&#x80FD;AC&#x3002;&#x540C;&#x65F6;&#x8FD9;&#x4E2A;&#x4E5F;&#x662F;&#x300A;&#x5251;&#x6307;offer&#x300B;&#x4E66;&#x4E0A;&#x6CA1;&#x6709;&#x5199;&#x7684;&#xFF0C;&#x5E0C;&#x671B;&#x80FD;&#x5F15;&#x8D77;&#x5927;&#x5BB6;&#x7684;&#x6CE8;&#x610F;&#x3002;</p>
<pre><code class="lang-python"><span class="hljs-comment"># -*- coding:utf-8 -*-</span>
<span class="hljs-comment"># class TreeNode:</span>
<span class="hljs-comment">#     def __init__(self, x):</span>
<span class="hljs-comment">#         self.val = x</span>
<span class="hljs-comment">#         self.left = None</span>
<span class="hljs-comment">#         self.right = None</span>
<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">HasSubtree</span><span class="hljs-params">(self, pRoot1, pRoot2)</span>:</span>
        <span class="hljs-comment"># write code here</span>
        <span class="hljs-comment">#&#x5224;&#x65AD;&#x5982;&#x679C; &#x4E8C;&#x53C9;&#x6811;&#x662F;&#x4E0D;&#x662F;&#x7A7A;&#x6811;&#xFF0C;&#x5982;&#x679C;&#x662F;&#x4E24;&#x4E2A;&#x4E2D;&#x4EFB;&#x4F55;&#x4E00;&#x4E2A;&#x662F;&#x7A7A;&#x6811;&#xFF0C;&#x5C31;&#x8FD4;&#x56DE; none</span>
        <span class="hljs-keyword">if</span> pRoot2 == <span class="hljs-keyword">None</span> <span class="hljs-keyword">or</span> pRoot1 == <span class="hljs-keyword">None</span>:
            <span class="hljs-keyword">return</span> <span class="hljs-keyword">False</span>
        <span class="hljs-comment">#&#x5BF9;&#x4E8E;&#x4E24;&#x68F5;&#x4E8C;&#x53C9;&#x6811;&#x6765;&#x8BF4;&#xFF0C;&#x8981;&#x5224;&#x65AD;B&#x662F;&#x4E0D;&#x662F;A&#x7684;&#x5B50;&#x7ED3;&#x6784;&#xFF0C;&#x9996;&#x5148;&#x7B2C;&#x4E00;&#x6B65;&#x5728;&#x6811;A&#x4E2D;&#x67E5;&#x627E;&#x4E0E;B&#x6839;&#x8282;&#x70B9;&#x7684;&#x503C;&#x4E00;&#x6837;&#x7684;&#x8282;&#x70B9;&#x3002;</span>
        <span class="hljs-comment">#&#x5B9A;&#x4E49;&#x4E00;&#x4E2A;&#x51FD;&#x6570;&#xFF0C;&#x6765;&#x627E; &#x76F8;&#x7B49;&#x7684;&#x7ED3;&#x70B9;</span>
        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">hasEqual</span><span class="hljs-params">(pRoot1, pRoot2)</span>:</span>
            <span class="hljs-keyword">if</span> pRoot2 == <span class="hljs-keyword">None</span>:
                <span class="hljs-keyword">return</span> <span class="hljs-keyword">True</span>
            <span class="hljs-keyword">if</span> pRoot1 == <span class="hljs-keyword">None</span>:
                <span class="hljs-keyword">return</span> <span class="hljs-keyword">False</span>
            <span class="hljs-comment">#&#x5982;&#x679C;&#x8FD9;&#x4E24;&#x4E2A;&#x7ED3;&#x70B9;&#x7684;&#x503C;&#x76F8;&#x7B49;&#x7684;&#x8BDD;</span>
            <span class="hljs-keyword">if</span> pRoot1.val == pRoot2.val:
                <span class="hljs-comment">#&#xFF0C;&#x518D;&#x5224;&#x65AD;&#x5B50;&#x4E8C;&#x53C9;&#x6811;&#x7684;&#x5DE6;&#x8282;&#x70B9;&#x662F;&#x4E0D;&#x662F;&#x7A7A;&#xFF0C;&#x5982;&#x679C;&#x662F;&#x7A7A;&#x7684;&#x8BDD;&#xFF0C;&#x90A3;&#x4E48;&#x5DE6;&#x8282;&#x70B9;&#x5C31;&#x76F8;&#x7B49;&#xFF0C;&#x8FD4;&#x56DE;&#x771F; true</span>
                <span class="hljs-keyword">if</span> pRoot2.left == <span class="hljs-keyword">None</span>:
                    leftEqual = <span class="hljs-keyword">True</span>
                <span class="hljs-keyword">else</span>:
                    <span class="hljs-comment">#&#x5982;&#x679C;&#x4E0D;&#x662F;&#x7A7A;&#x7684;&#x8BDD;&#xFF0C;&#x518D;&#x5224;&#x65AD;&#x6BCD;&#x4E8C;&#x53C9;&#x6811;&#x548C;&#x5B50;&#x4E8C;&#x53C9;&#x6811;&#x7684;&#x5DE6;&#x8282;&#x70B9;&#x662F;&#x5426;&#x76F8;&#x7B49;</span>
                    leftEqual = hasEqual(pRoot1.left, pRoot2.left)
                <span class="hljs-comment">#&#x7136;&#x540E;&#x5224;&#x65AD; &#x5B50;&#x4E8C;&#x53C9;&#x6811;&#x7684; &#x53F3;&#x7ED3;&#x70B9;&#x662F;&#x4E0D;&#x662F;&#x7A7A;&#xFF0C;&#x5982;&#x679C;&#x662F;&#x7A7A;&#x7684;&#x8BDD;&#xFF0C;&#x90A3;&#x4E48;&#x53F3;&#x7ED3;&#x70B9;&#x5C31;&#x76F8;&#x7B49;&#xFF0C;&#x8FD4;&#x56DE; true</span>
                <span class="hljs-keyword">if</span> pRoot2.right == <span class="hljs-keyword">None</span>:
                    rightEqual = <span class="hljs-keyword">True</span>
                <span class="hljs-keyword">else</span>:
                    <span class="hljs-comment">#&#x5982;&#x679C;&#x4E0D;&#x662F;&#x7A7A;&#x7684;&#x8BDD;&#xFF0C;&#x5C31;&#x9012;&#x5F52;&#xFF0C;&#x7EE7;&#x7EED;&#x53BB;&#x5224;&#x65AD; &#x6BCD;&#x4E8C;&#x53C9;&#x6811;&#x7684;&#x53F3;&#x7ED3;&#x70B9;&#x548C;&#x5B50;&#x4E8C;&#x53C9;&#x6811;&#x7684;&#x53F3;&#x7ED3;&#x70B9;</span>
                    rightEqual = hasEqual(pRoot1.right, pRoot2.right)
                <span class="hljs-comment">#&#x6700;&#x540E;&#x8FD4;&#x56DE;&#x7684;&#x662F; &#x5224;&#x65AD; &#x5DE6;&#x53F3; &#x662F;&#x4E0D;&#x662F;&#x76F8;&#x7B49; &#x7684;&#x5224;&#x65AD;&#x7ED3;&#x679C;&#xFF0C;&#x5F53;&#x4E24;&#x4E2A;&#x540C;&#x65F6;&#x4E3A;&#x771F;&#x7684;&#x65F6;&#x5019;&#xFF0C;&#x8FD9;&#x4E2A;&#x5B50;&#x4E8C;&#x53C9;&#x6811;&#xFF0C;&#x5C31;&#x662F;&#x6BCD;&#x4E8C;&#x53C9;&#x6811;&#x7684;&#x5B50;&#x4E8C;&#x53C9;&#x6811;&#xFF0C;&#x6709;&#x4E00;&#x4E2A;&#x4E3A;&#x5047; &#x5219; &#x4E3A;&#x5047;&#x3002;</span>
                <span class="hljs-keyword">return</span> leftEqual <span class="hljs-keyword">and</span> rightEqual
            <span class="hljs-comment">#&#x5982;&#x679C;&#x8FD9;&#x4E24;&#x4E2A;&#x7ED3;&#x70B9;&#x7684;&#x503C;&#x4E0D;&#x76F8;&#x7B49;&#x7684;&#x8BDD;&#xFF0C;&#x90A3;&#x5C31;&#x8FD4;&#x56DE; &#x5047;&#xFF0C;&#x8FD9;&#x662F;&#x6765;&#x627E; &#x662F;&#x4E0D;&#x662F;&#x76F8;&#x7B49;&#x7684;&#x51FD;&#x6570;</span>
            <span class="hljs-keyword">return</span> <span class="hljs-keyword">False</span>
        <span class="hljs-comment">#&#x5224;&#x65AD;&#x5982;&#x679C;&#x8BF4;&#x8FD9;&#x4E2A;&#x4E24;&#x4E2A; &#x4E8C;&#x53C9;&#x6811;&#x7684;&#x6839;&#x8282;&#x70B9;&#x503C;&#x76F8;&#x7B49;&#x7684;&#x8BDD;&#xFF0C;&#x90A3;&#x4E48;&#x5C31;&#x8C03;&#x7528;&#x4E0A;&#x9762;&#x7684;&#x51FD;&#x6570;&#xFF0C;&#x7136;&#x540E;&#x6765; &#x7EE7;&#x7EED;&#x5224;&#x65AD;&#x540E;&#x9762;&#x7684; &#x662F;&#x5426;&#x6709; &#x5DE6;&#x6811;&#xFF0C;&#x53F3;&#x6811;&#x7B49;&#x7B49;&#x3002;&#x3002;&#x3002;</span>
        <span class="hljs-keyword">if</span> pRoot1.val == pRoot2.val:
            <span class="hljs-comment">#&#x8C03;&#x7528; &#x51FD;&#x6570;&#x5224;&#x65AD;&#x662F;&#x5426;&#x76F8;&#x7B49;</span>
            ret = hasEqual(pRoot1, pRoot2)
            <span class="hljs-comment">#&#x5982;&#x679C;&#x8FD4;&#x56DE;&#x7684;&#x662F;&#x4E00;&#x4E2A;true&#x7684;&#x8BDD;</span>
            <span class="hljs-keyword">if</span> ret:
                &#x5C31;&#x8FD4;&#x56DE; true
                <span class="hljs-keyword">return</span> <span class="hljs-keyword">True</span>
        <span class="hljs-comment">#&#x5982;&#x679C;&#x6839;&#x8282;&#x70B9;&#x4E0D;&#x7B49;&#x7684;&#x8BDD;&#xFF0C;&#x90A3;&#x5C31;&#x5224;&#x65AD; &#x6BCD;&#x4E8C;&#x53C9;&#x6811;&#x7684;&#x5DE6;&#x5B50;&#x6811;&#xFF0C;&#x662F;&#x4E0D;&#x662F;&#x4E0E; &#x8981;&#x5224;&#x65AD;&#x7684; &#x4E8C;&#x53C9;&#x6811; &#x76F8;&#x7B49;</span>
        <span class="hljs-comment">#&#x5224;&#x65AD; &#x5DE6; &#x6811; &#x662F;&#x4E0D;&#x662F;&#x76F8;&#x7B49;&#x7684;&#x8BDD;</span>
        ret = self.HasSubtree(pRoot1.left, pRoot2)
        <span class="hljs-keyword">if</span> ret:
            <span class="hljs-keyword">return</span> <span class="hljs-keyword">True</span>
        <span class="hljs-comment">#&#x5982;&#x679C;&#x5DE6;&#x5B50;&#x6811;&#x4E0D;&#x7B49;&#x7684;&#x8BDD;&#xFF0C;&#x90A3;&#x5C31;&#x5224;&#x65AD; &#x6BCD;&#x4E8C;&#x53C9;&#x6811;&#x7684;&#x53F3;&#x5B50;&#x6811;&#xFF0C;&#x662F;&#x4E0D;&#x662F;&#x4E0E; &#x8981;&#x5224;&#x65AD;&#x7684; &#x4E8C;&#x53C9;&#x6811; &#x76F8;&#x7B49;</span>
        ret = self.HasSubtree(pRoot1.right, pRoot2)
        <span class="hljs-keyword">return</span> ret



<span class="hljs-comment"># -*- coding:utf-8 -*-</span>
<span class="hljs-comment"># class TreeNode:</span>
<span class="hljs-comment">#     def __init__(self, x):</span>
<span class="hljs-comment">#         self.val = x</span>
<span class="hljs-comment">#         self.left = None</span>
<span class="hljs-comment">#         self.right = None</span>
<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution2</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">HasSubtree</span><span class="hljs-params">(self, pRoot1, pRoot2)</span>:</span>
        <span class="hljs-comment"># write code here</span>
        result = <span class="hljs-keyword">False</span>
        <span class="hljs-keyword">if</span> pRoot1 != <span class="hljs-keyword">None</span> <span class="hljs-keyword">and</span> pRoot2 != <span class="hljs-keyword">None</span>:
            <span class="hljs-keyword">if</span> pRoot1.val == pRoot2.val:
                result = self.DoesTree1haveTree2(pRoot1, pRoot2)
            <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> result:
                result = self.HasSubtree(pRoot1.left, pRoot2)
            <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> result:
                result = self.HasSubtree(pRoot1.right, pRoot2)
        <span class="hljs-keyword">return</span> result
    <span class="hljs-comment"># &#x7528;&#x4E8E;&#x9012;&#x5F52;&#x5224;&#x65AD;&#x6811;&#x7684;&#x6BCF;&#x4E2A;&#x8282;&#x70B9;&#x662F;&#x5426;&#x76F8;&#x540C;</span>
    <span class="hljs-comment"># &#x9700;&#x8981;&#x6CE8;&#x610F;&#x7684;&#x5730;&#x65B9;&#x662F;: &#x524D;&#x4E24;&#x4E2A;if&#x8BED;&#x53E5;&#x4E0D;&#x53EF;&#x4EE5;&#x98A0;&#x5012;&#x987A;&#x5E8F;</span>
    <span class="hljs-comment"># &#x5982;&#x679C;&#x98A0;&#x5012;&#x987A;&#x5E8F;, &#x4F1A;&#x5148;&#x5224;&#x65AD;pRoot1&#x662F;&#x5426;&#x4E3A;None, &#x5176;&#x5B9E;&#x8FD9;&#x4E2A;&#x65F6;&#x5019;pRoot2&#x7684;&#x7ED3;&#x70B9;&#x5DF2;&#x7ECF;&#x904D;&#x5386;&#x5B8C;&#x6210;&#x786E;&#x5B9A;&#x76F8;&#x7B49;&#x4E86;, &#x4F46;&#x662F;&#x8FD4;&#x56DE;&#x4E86;False, &#x5224;&#x65AD;&#x9519;&#x8BEF;</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">DoesTree1haveTree2</span><span class="hljs-params">(self, pRoot1, pRoot2)</span>:</span>
        <span class="hljs-keyword">if</span> pRoot2 == <span class="hljs-keyword">None</span>:
            <span class="hljs-keyword">return</span> <span class="hljs-keyword">True</span>
        <span class="hljs-keyword">if</span> pRoot1 == <span class="hljs-keyword">None</span>:
            <span class="hljs-keyword">return</span> <span class="hljs-keyword">False</span>
        <span class="hljs-keyword">if</span> pRoot1.val != pRoot2.val:
            <span class="hljs-keyword">return</span> <span class="hljs-keyword">False</span>
        <span class="hljs-keyword">return</span> self.DoesTree1haveTree2(pRoot1.left, pRoot2.left) <span class="hljs-keyword">and</span> self.DoesTree1haveTree2(pRoot1.right, pRoot2.right)
</code></pre>
<hr>
<h2 id="27&#x4E8C;&#x53C9;&#x6811;&#x7684;&#x955C;&#x50CF;">27.&#x4E8C;&#x53C9;&#x6811;&#x7684;&#x955C;&#x50CF;</h2>
<p><strong>&#x64CD;&#x4F5C;&#x7ED9;&#x5B9A;&#x7684;&#x4E8C;&#x53C9;&#x6811;&#xFF0C;&#x5C06;&#x5176;&#x53D8;&#x6362;&#x4E3A;&#x6E90;&#x4E8C;&#x53C9;&#x6811;&#x7684;&#x955C;&#x50CF;&#x3002;</strong></p>
<h5 id="&#x8F93;&#x5165;&#x63CF;&#x8FF0;"><code>&#x8F93;&#x5165;&#x63CF;&#x8FF0;:</code></h5>
<pre><code class="lang-python">&#x4E8C;&#x53C9;&#x6811;&#x7684;&#x955C;&#x50CF;&#x5B9A;&#x4E49;&#xFF1A;&#x6E90;&#x4E8C;&#x53C9;&#x6811; 
            <span class="hljs-number">8</span>
           /  \
          <span class="hljs-number">6</span>   <span class="hljs-number">10</span>
         / \  / \
        <span class="hljs-number">5</span>  <span class="hljs-number">7</span> <span class="hljs-number">9</span> <span class="hljs-number">11</span>
        &#x955C;&#x50CF;&#x4E8C;&#x53C9;&#x6811;
            <span class="hljs-number">8</span>
           /  \
          <span class="hljs-number">10</span>   <span class="hljs-number">6</span>
         / \  / \
        <span class="hljs-number">11</span> <span class="hljs-number">9</span> <span class="hljs-number">7</span>  <span class="hljs-number">5</span>
</code></pre>
<hr>
<p>&#x4E8C;&#x53C9;&#x6811;&#x7684;&#x955C;&#x50CF;&#xFF0C;&#x5C31;&#x662F;&#x5DE6;&#x53F3; &#x5B50;&#x6811; &#x8C03;&#x6362;&#x4F4D;&#x7F6E;&#xFF0C;&#x7136;&#x540E;&#x7528;&#x9012;&#x5F52;&#x7684;&#x65B9;&#x5F0F;&#x6765; &#x5FAA;&#x73AF;&#x904D;&#x5386; &#x5904;&#x7406;&#x6839;&#x8282;&#x70B9;&#x5DE6;&#x5B50;&#x6811;&#x7684;&#x5DE6;&#x5B50;&#x6811;&#x3002;&#x3002;&#x6839;&#x8282;&#x70B9;&#x53F3;&#x5B50;&#x6811;&#x7684;&#x53F3;&#x5B50;&#x6811;&#x6765;&#x8C03;&#x6362;&#x4F4D;&#x7F6E;  &#x3002;&#x3002;&#x3002;&#x4F9D;&#x6B21;&#x9012;&#x5F52;&#x5FAA;&#x73AF;</p>
<pre><code class="lang-python"><span class="hljs-comment"># -*- coding:utf-8 -*-</span>
<span class="hljs-comment"># class TreeNode:</span>
<span class="hljs-comment">#     def __init__(self, x):</span>
<span class="hljs-comment">#         self.val = x</span>
<span class="hljs-comment">#         self.left = None</span>
<span class="hljs-comment">#         self.right = None</span>
<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-comment"># &#x8FD4;&#x56DE;&#x955C;&#x50CF;&#x6811;&#x7684;&#x6839;&#x8282;&#x70B9;</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">Mirror</span><span class="hljs-params">(self, root)</span>:</span>
        <span class="hljs-comment"># write code here</span>
        <span class="hljs-comment">#&#x5982;&#x679C;&#x662F;&#x6839;&#x8282;&#x70B9;&#x4E3A;&#x7A7A;&#x7684;&#x8BDD;&#xFF0C;&#x76F4;&#x63A5;&#x5C31;&#x8FD4;&#x56DE;&#x7A7A;</span>
        <span class="hljs-keyword">if</span> root == <span class="hljs-keyword">None</span>:
            <span class="hljs-keyword">return</span> <span class="hljs-keyword">None</span>
        <span class="hljs-comment">#&#x5904;&#x7406;&#x6839;&#x8282;&#x70B9;&#xFF0C;&#x6839;&#x8282;&#x70B9;&#x7684;&#x5DE6;&#x5B50;&#x6811;&#x548C;&#x53F3;&#x5B50;&#x6811;&#x6765;&#x8C03;&#x6362;&#x4F4D;&#x7F6E;&#x3002;</span>
        root.left,root.right = root.right,root.left
        <span class="hljs-comment">#&#x5904;&#x7406;&#x6839;&#x8282;&#x70B9;&#x5DE6;&#x5B50;&#x6811;&#x7684;&#x5DE6;&#x5B50;&#x6811; &#x505A;&#x9012;&#x5F52; &#x5FAA;&#x73AF;</span>
        self.Mirror(root.left)
        <span class="hljs-comment">#&#x5904;&#x7406;&#x6839;&#x8282;&#x70B9;&#x53F3;&#x5B50;&#x6811;&#x7684;&#x53F3;&#x5B50;&#x6811; &#x505A;&#x9012;&#x5F52; &#x5FAA;&#x73AF;</span>
        self.Mirror(root.right)
</code></pre>
<hr>
<h2 id="28&#x4ECE;&#x4E0A;&#x5F80;&#x4E0B;&#x6253;&#x5370;&#x4E8C;&#x53C9;&#x6811;">28.&#x4ECE;&#x4E0A;&#x5F80;&#x4E0B;&#x6253;&#x5370;&#x4E8C;&#x53C9;&#x6811;</h2>
<p><strong>&#x4ECE;&#x4E0A;&#x5F80;&#x4E0B;&#x6253;&#x5370;&#x51FA;&#x4E8C;&#x53C9;&#x6811;&#x7684;&#x6BCF;&#x4E2A;&#x8282;&#x70B9;&#xFF0C;&#x540C;&#x5C42;&#x8282;&#x70B9;&#x4ECE;&#x5DE6;&#x81F3;&#x53F3;&#x6253;&#x5370;&#x3002;</strong></p>
<pre><code class="lang-python"><span class="hljs-comment"># -*- coding:utf-8 -*-</span>
<span class="hljs-comment"># class TreeNode:</span>
<span class="hljs-comment">#     def __init__(self, x):</span>
<span class="hljs-comment">#         self.val = x</span>
<span class="hljs-comment">#         self.left = None</span>
<span class="hljs-comment">#         self.right = None</span>
<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-comment"># &#x8FD4;&#x56DE;&#x4ECE;&#x4E0A;&#x5230;&#x4E0B;&#x6BCF;&#x4E2A;&#x8282;&#x70B9;&#x503C;&#x5217;&#x8868;&#xFF0C;&#x4F8B;&#xFF1A;[1,2,3]</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">PrintFromTopToBottom</span><span class="hljs-params">(self, root)</span>:</span>
        <span class="hljs-comment"># write code here</span>
        <span class="hljs-comment">#&#x5148;&#x5224;&#x65AD; &#x662F;&#x4E0D;&#x662F;&#x7A7A;</span>
        <span class="hljs-keyword">if</span> root == <span class="hljs-keyword">None</span>:
            <span class="hljs-comment">#&#x7A7A;&#x7684;&#x8BDD; &#x4F9D;&#x9898;&#x610F;&#x8981;&#x6C42; &#x8FD4;&#x56DE; &#x3010;&#x3011;</span>
            <span class="hljs-keyword">return</span> []
        <span class="hljs-comment">#&#x9700;&#x8981;&#x4E00;&#x4E2A;&#x8F85;&#x52A9;&#x5217;&#x8868; &#x7ED9;&#x4E00;&#x4E2A; &#x6839;&#x8282;&#x70B9;</span>
        treeNodeTmp = [root]
        <span class="hljs-comment">#&#x9700;&#x8981;&#x4E00;&#x4E2A;&#x8FD4;&#x56DE;&#x7684; &#x6570;&#x7EC4;</span>
        ret = []
        <span class="hljs-comment">#&#x5FAA;&#x73AF; &#x5F53; &#x6211;&#x4EEC;&#x8FD9;&#x4E2A;&#x8F85;&#x52A9;&#x7684; &#x5217;&#x8868;&#x4E0D;&#x4E3A;&#x7A7A;&#x7684;&#x65F6;&#x5019;</span>
        <span class="hljs-keyword">while</span> treeNodeTmp:
            <span class="hljs-comment">#&#x628A; &#x8F85;&#x52A9;&#x7684;&#x5217;&#x8868; &#x53D6;&#x51FA;&#x7B2C;&#x4E00;&#x4E2A;&#x503C;</span>
            tmpNode = treeNodeTmp[<span class="hljs-number">0</span>]
            <span class="hljs-comment">#&#x7B2C;&#x4E00;&#x4E2A;&#x7ED3;&#x70B9;&#x7684;&#x503C; &#x52A0;&#x5165;&#x5230; &#x8FD4;&#x56DE;&#x7684;&#x6570;&#x7EC4;&#x4E2D;</span>
            ret.append(tmpNode.val)
            <span class="hljs-comment">#&#x5982;&#x679C;&#x8BF4; &#x8FD9;&#x4E2A;&#x7ED3;&#x70B9;&#x7684;&#x5DE6;&#x5B50;&#x6811;&#x5B58;&#x5728;&#x7684;&#x8BDD;&#xFF0C;&#x90A3;&#x4E48;&#x5C31;&#x628A;&#x8FD9;&#x4E2A;&#x5DE6;&#x7ED3;&#x70B9;&#x6DFB;&#x52A0;&#x5230;&#x8FD9;&#x4E2A;&#x8FD4;&#x56DE;&#x7684;&#x5217;&#x8868;&#x4E2D;</span>
            <span class="hljs-keyword">if</span> tmpNode.left:
                treeNodeTmp.append(tmpNode.left)
            <span class="hljs-comment">#&#x5982;&#x679C;&#x8FD9;&#x4E2A;&#x7ED3;&#x70B9;&#x7684;&#x53F3;&#x5B50;&#x6811;&#x5B58;&#x5728;&#x7684;&#x8BDD;&#xFF0C;&#x90A3;&#x4E48;&#x5C31;&#x628A;&#x8FD9;&#x4E2A;&#x53F3;&#x7ED3;&#x70B9;&#x6DFB;&#x52A0;&#x5230;&#x8FD9;&#x4E2A;&#x8FD4;&#x56DE;&#x7684;&#x5217;&#x8868;&#x4E2D;</span>
            <span class="hljs-keyword">if</span> tmpNode.right:
                treeNodeTmp.append(tmpNode.right)
            <span class="hljs-comment">#&#x5220;&#x9664;&#x6389;&#x8F85;&#x52A9;&#x5217;&#x8868;&#x7684;&#x7B2C;&#x4E00;&#x4E2A;&#x503C;&#xFF0C;&#x4E3A;&#x4EC0;&#x4E48;&#x5220;&#x6389;&#x7B2C;&#x4E00;&#x4E2A;&#xFF0C;&#x662F;&#x56E0;&#x4E3A;&#x6211;&#x4EEC;&#x5DF2;&#x7ECF;&#x628A;&#x8F85;&#x52A9;&#x5217;&#x8868;&#x4E2D;&#x7684;&#x7B2C;&#x4E00;&#x4E2A;&#x503C;&#x52A0;&#x5165;&#x5230;&#x6211;&#x4EEC;&#x8981;&#x8FD4;&#x56DE;&#x7684;&#x6570;&#x7EC4;&#x4E2D;&#x4E86;&#xFF0C;&#x6BCF;&#x6B21;&#x53EA;&#x6DFB;&#x52A0;&#x4E86;&#x4E00;&#x4E2A;&#xFF0C;&#x800C;&#x4E14;&#x6BCF;&#x6B21;&#x4E5F;&#x53EA;&#x5FAA;&#x73AF;&#x5224;&#x65AD;&#x4E86;&#x4E00;&#x4E2A;&#x7ED3;&#x70B9;&#x7684;&#x5DE6;&#x53F3;&#x5B50;&#x6811;&#x3002;</span>
            <span class="hljs-keyword">del</span> treeNodeTmp[<span class="hljs-number">0</span>]
        <span class="hljs-comment">#&#x6700;&#x540E;&#x8FD4;&#x56DE;&#x6211;&#x4EEC;&#x7684;&#x8FD4;&#x56DE;&#x6570;&#x7EC4;</span>
        <span class="hljs-keyword">return</span> ret
</code></pre>
<hr>
<h2 id="29&#x4E8C;&#x53C9;&#x641C;&#x7D22;&#x6811;&#x7684;&#x540E;&#x5E8F;&#x904D;&#x5386;&#x5E8F;&#x5217;">29.&#x4E8C;&#x53C9;&#x641C;&#x7D22;&#x6811;&#x7684;&#x540E;&#x5E8F;&#x904D;&#x5386;&#x5E8F;&#x5217;</h2>
<p><strong>&#x8F93;&#x5165;&#x4E00;&#x4E2A;&#x6574;&#x6570;&#x6570;&#x7EC4;&#xFF0C;&#x5224;&#x65AD;&#x8BE5;&#x6570;&#x7EC4;&#x662F;&#x4E0D;&#x662F;&#x67D0;&#x4E8C;&#x53C9;&#x641C;&#x7D22;&#x6811;&#x7684;&#x540E;&#x5E8F;&#x904D;&#x5386;&#x7684;&#x7ED3;&#x679C;&#x3002;&#x5982;&#x679C;&#x662F;&#x5219;&#x8F93;&#x51FA;Yes,&#x5426;&#x5219;&#x8F93;&#x51FA;No&#x3002;&#x5047;&#x8BBE;&#x8F93;&#x5165;&#x7684;&#x6570;&#x7EC4;&#x7684;&#x4EFB;&#x610F;&#x4E24;&#x4E2A;&#x6570;&#x5B57;&#x90FD;&#x4E92;&#x4E0D;&#x76F8;&#x540C;&#x3002;</strong></p>
<h5 id="&#x4EC0;&#x4E48;&#x53EB;&#x4E8C;&#x53C9;&#x641C;&#x7D22;&#x6811;&#xFF1F;">&#x4EC0;&#x4E48;&#x53EB;&#x4E8C;&#x53C9;&#x641C;&#x7D22;&#x6811;&#xFF1F;</h5>
<p>&#x4E8C;&#x53C9;&#x67E5;&#x627E;&#x6811;&#xFF08;Binary Search Tree&#xFF09;&#xFF0C;&#xFF08;&#x53C8;&#xFF1A;<a href="https://baike.baidu.com/item/%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91/7077855" target="_blank">&#x4E8C;&#x53C9;&#x641C;&#x7D22;&#x6811;</a>&#xFF0C;&#x4E8C;&#x53C9;&#x6392;&#x5E8F;&#x6811;&#xFF09;&#x5B83;&#x6216;&#x8005;&#x662F;&#x4E00;&#x68F5;&#x7A7A;&#x6811;&#xFF0C;&#x6216;&#x8005;&#x662F;&#x5177;&#x6709;&#x4E0B;&#x5217;&#x6027;&#x8D28;&#x7684;<a href="https://baike.baidu.com/item/%E4%BA%8C%E5%8F%89%E6%A0%91/1602879" target="_blank">&#x4E8C;&#x53C9;&#x6811;</a>&#xFF1A; &#x82E5;&#x5B83;&#x7684;&#x5DE6;&#x5B50;&#x6811;&#x4E0D;&#x7A7A;&#xFF0C;&#x5219;&#x5DE6;&#x5B50;&#x6811;&#x4E0A;&#x6240;&#x6709;&#x7ED3;&#x70B9;&#x7684;&#x503C;&#x5747;&#x5C0F;&#x4E8E;&#x5B83;&#x7684;&#x6839;&#x7ED3;&#x70B9;&#x7684;&#x503C;&#xFF1B; &#x82E5;&#x5B83;&#x7684;&#x53F3;&#x5B50;&#x6811;&#x4E0D;&#x7A7A;&#xFF0C;&#x5219;&#x53F3;&#x5B50;&#x6811;&#x4E0A;&#x6240;&#x6709;&#x7ED3;&#x70B9;&#x7684;&#x503C;&#x5747;&#x5927;&#x4E8E;&#x5B83;&#x7684;&#x6839;&#x7ED3;&#x70B9;&#x7684;&#x503C;&#xFF1B; &#x5B83;&#x7684;&#x5DE6;&#x3001;&#x53F3;&#x5B50;&#x6811;&#x4E5F;&#x5206;&#x522B;&#x4E3A;<a href="https://baike.baidu.com/item/%E4%BA%8C%E5%8F%89%E6%8E%92%E5%BA%8F%E6%A0%91/10905079" target="_blank">&#x4E8C;&#x53C9;&#x6392;&#x5E8F;&#x6811;</a>&#x3002;</p>
<p>&#x601D;&#x8DEF;&#xFF1A;&#x4E8C;&#x53C9;&#x641C;&#x7D22;&#x6811;&#x7684;&#x5B9A;&#x4E49;&#x5982;&#x4E0A;&#x6240;&#x793A;&#xFF0C;&#x90A3;&#x4E48;&#x8BF4; &#x6211;&#x4EEC;&#x53EF;&#x4EE5;&#x6839;&#x636E;&#x4E8C;&#x53C9;&#x641C;&#x7D22;&#x6811;&#x7684;&#x540E;&#x5E8F;&#x904D;&#x5386;&#x6765;&#x5F97;&#x51FA;&#xFF0C;&#x540E;&#x5E8F;&#x904D;&#x5386;&#x5F97;&#x5230;&#x7684;&#x6700;&#x540E;&#x4E00;&#x4E2A;&#x503C;&#x662F;&#x6839;&#x8282;&#x70B9;&#xFF0C;&#x90A3;&#x4E48; &#x5728;&#x904D;&#x5386;&#x7ED3;&#x679C;&#x7684;&#x524D;&#x534A;&#x90E8;&#x5206;&#x662F;&#x4E8C;&#x53C9;&#x641C;&#x7D22;&#x6811;&#x7684;&#x5DE6;&#x5B50;&#x6811;&#xFF0C;&#x90FD;&#x6BD4;&#x6839;&#x8282;&#x70B9; &#x5C0F;&#xFF0C;&#x540E;&#x534A;&#x90E8;&#x5206;&#x90FD;&#x6BD4;&#x6839;&#x8282;&#x70B9;&#x5927;&#xFF0C;</p>
<pre><code class="lang-python"><span class="hljs-string">&quot;&quot;&quot;
python:&#x540E;&#x5E8F;&#x904D;&#x5386; &#x7684;&#x5E8F;&#x5217;&#x4E2D;&#xFF0C;&#x6700;&#x540E;&#x4E00;&#x4E2A;&#x6570;&#x5B57;&#x662F;&#x6811;&#x7684;&#x6839;&#x8282;&#x70B9; &#xFF0C;&#x6570;&#x7EC4;&#x4E2D;&#x524D;&#x9762;&#x7684;&#x6570;&#x5B57;&#x53EF;&#x4EE5;&#x5206;&#x4E3A;&#x4E24;&#x90E8;&#x5206;&#xFF1A;&#x7B2C;&#x4E00;&#x90E8;&#x5206;&#x662F;&#x5DE6;&#x5B50;&#x6811;&#x8282;&#x70B9; &#x7684;&#x503C;&#xFF0C;&#x90FD;&#x6BD4;&#x6839;&#x8282;&#x70B9;&#x7684;&#x503C;&#x5C0F;&#xFF1B;&#x7B2C;&#x4E8C;&#x90E8;&#x5206; &#x662F;&#x53F3;&#x5B50;&#x6811; &#x8282;&#x70B9;&#x7684;&#x503C;&#xFF0C;&#x90FD;&#x6BD4; &#x6839; &#x8282;&#x70B9; &#x7684;&#x503C;&#x5927;&#xFF0C;&#x540E;&#x9762;&#x7528;&#x9012;&#x5F52;&#x5206;&#x522B;&#x5224;&#x65AD;&#x524D;&#x540E;&#x4E24;&#x90E8;&#x5206; &#x662F;&#x5426; &#x7B26;&#x5408;&#x4EE5;&#x4E0A;&#x539F;&#x5219;

&quot;&quot;&quot;</span>


<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">VerifySquenceOfBST</span><span class="hljs-params">(self, sequence)</span>:</span>
        <span class="hljs-comment"># write code here</span>
        <span class="hljs-comment">#&#x5224;&#x65AD;&#x8FD9;&#x4E2A;&#x540E;&#x5E8F;&#x904D;&#x5386;&#x7684;&#x7ED3;&#x679C;&#x662F;&#x4E0D;&#x662F;&#x7A7A;&#xFF0C;&#x5982;&#x679C;&#x662F;&#x7A7A;&#x7684;&#x8BDD;&#xFF0C;&#x5C31;&#x8FD4;&#x56DE;&#x5047;&#xFF0C;&#x5982;&#x679C;&#x8FD9;&#x4E2A;&#x6570;&#x7EC4;&#x7684;&#x957F;&#x5EA6;&#x7B49;&#x4E8E;0</span>
        <span class="hljs-comment">#&#x7684;&#x8BDD;&#xFF0C;&#x5C31;&#x8BF4;&#x660E;&#x662F;&#x8FD9;&#x4E2A;&#x6570;&#x7EC4;&#x4E3A;&#x7A7A;&#xFF0C;&#x90A3;&#x4E48;&#x4E5F;&#x8FD4;&#x56DE;&#x5047;</span>
        <span class="hljs-keyword">if</span> sequence==<span class="hljs-keyword">None</span> <span class="hljs-keyword">or</span> len(sequence)==<span class="hljs-number">0</span>:
            <span class="hljs-keyword">return</span> <span class="hljs-keyword">False</span>
        <span class="hljs-comment">#&#x6570;&#x7EC4;&#x7684;&#x957F;&#x5EA6;</span>
        length=len(sequence)
        <span class="hljs-comment">#&#x6839;&#x636E; &#x540E;&#x5E8F;&#x904D;&#x5386; &#x6839;&#x8282;&#x70B9; &#x5C31;&#x662F;&#x6570;&#x7EC4; &#x7684; &#x6700;&#x540E;&#x4E00;&#x4E2A;&#x503C;</span>
        root=sequence[length-<span class="hljs-number">1</span>]
        <span class="hljs-comment"># &#x5728;&#x4E8C;&#x53C9;&#x641C;&#x7D22; &#x6811;&#x4E2D; &#x5DE6;&#x5B50;&#x6811;&#x8282;&#x70B9;&#x5C0F;&#x4E8E;&#x6839;&#x8282;&#x70B9;</span>
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(length):
            <span class="hljs-keyword">if</span> sequence[i]&gt;root:
                <span class="hljs-keyword">break</span>
        <span class="hljs-comment"># &#x4E8C;&#x53C9;&#x641C;&#x7D22;&#x6811;&#x4E2D;&#x53F3;&#x5B50;&#x6811;&#x7684;&#x8282;&#x70B9;&#x90FD;&#x5927;&#x4E8E;&#x6839;&#x8282;&#x70B9;</span>
        <span class="hljs-keyword">for</span> j  <span class="hljs-keyword">in</span> range(i,length):
            <span class="hljs-keyword">if</span> sequence[j]&lt;root:
                <span class="hljs-keyword">return</span> <span class="hljs-keyword">False</span>
        <span class="hljs-comment"># &#x5224;&#x65AD;&#x5DE6;&#x5B50;&#x6811;&#x662F;&#x5426;&#x4E3A;&#x4E8C;&#x53C9;&#x6811;</span>
        left=<span class="hljs-keyword">True</span>
        <span class="hljs-keyword">if</span>  i&gt;<span class="hljs-number">0</span>:
            left=self.VerifySquenceOfBST(sequence[<span class="hljs-number">0</span>:i])
        <span class="hljs-comment"># &#x5224;&#x65AD; &#x53F3;&#x5B50;&#x6811;&#x662F;&#x5426;&#x4E3A;&#x4E8C;&#x53C9;&#x6811;</span>
        right=<span class="hljs-keyword">True</span>
        <span class="hljs-keyword">if</span> i&lt;length-<span class="hljs-number">1</span>:
            right=self.VerifySquenceOfBST(sequence[i:-<span class="hljs-number">1</span>])
        <span class="hljs-keyword">return</span> left <span class="hljs-keyword">and</span> right


<span class="hljs-comment"># -*- coding:utf-8 -*-</span>
<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution2</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">VerifySquenceOfBST</span><span class="hljs-params">(self, sequence)</span>:</span>
        <span class="hljs-comment"># write code here</span>
        <span class="hljs-comment">#&#x5224;&#x65AD;&#x8FD9;&#x4E2A;&#x540E;&#x5E8F;&#x904D;&#x5386;&#x7684;&#x7ED3;&#x679C;&#x662F;&#x4E0D;&#x662F;&#x7A7A;&#xFF0C;&#x5982;&#x679C;&#x662F;&#x7A7A;&#x7684;&#x8BDD;&#xFF0C;&#x5C31;&#x8FD4;&#x56DE;&#x5047;&#xFF0C;&#x5982;&#x679C;&#x8FD9;&#x4E2A;&#x6570;&#x7EC4;&#x7684;&#x957F;&#x5EA6;&#x7B49;&#x4E8E;0</span>
        <span class="hljs-comment">#&#x7684;&#x8BDD;&#xFF0C;&#x5C31;&#x8BF4;&#x660E;&#x662F;&#x8FD9;&#x4E2A;&#x6570;&#x7EC4;&#x4E3A;&#x7A7A;&#xFF0C;&#x90A3;&#x4E48;&#x4E5F;&#x8FD4;&#x56DE;&#x5047;</span>
        <span class="hljs-keyword">if</span> sequence == []:
            <span class="hljs-keyword">return</span> <span class="hljs-keyword">False</span>
        <span class="hljs-comment">#&#x6839;&#x636E; &#x540E;&#x5E8F;&#x904D;&#x5386; &#x6839;&#x8282;&#x70B9; &#x5C31;&#x662F;&#x6570;&#x7EC4; &#x7684; &#x6700;&#x540E;&#x4E00;&#x4E2A;&#x503C;</span>
        rootNum = sequence[-<span class="hljs-number">1</span>]
        <span class="hljs-comment">#&#x5220;&#x9664;&#x8FD9;&#x4E2A;&#x904D;&#x5386;&#x7684;&#x6570;&#x7EC4;&#x7684;&#x6700;&#x540E;&#x4E00;&#x4E2A;&#x503C; &#x4E5F;&#x5C31;&#x662F;&#x6839;&#x8282;&#x70B9;</span>
        <span class="hljs-keyword">del</span> sequence[-<span class="hljs-number">1</span>]
        <span class="hljs-comment">#&#x904D;&#x5386; &#x7D22;&#x5F15;&#x503C; &#x4E3A; &#x7A7A;</span>
        index = <span class="hljs-keyword">None</span>
        <span class="hljs-comment">#&#x904D;&#x5386;&#x5FAA;&#x73AF;&#x73B0;&#x5728;&#x7684;&#x8FD9;&#x4E2A; &#x540E;&#x5E8F;&#x904D;&#x5386;&#x7684;&#x6570;&#x7EC4;</span>
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(len(sequence)):
            <span class="hljs-comment">#&#x5982;&#x679C;&#x8BF4; &#x7D22;&#x5F15;&#x503C;&#x7B49;&#x4E8E;&#x7A7A;&#x800C;&#x4E14; &#x904D;&#x5386;&#x5F97;&#x5230;&#x7684;&#x6570;&#x7EC4;&#x7684;&#x90A3;&#x4E2A;&#x503C; &#x662F;&#x5927;&#x4E8E;&#x6211;&#x4EEC;&#x7684;&#x6839;&#x8282;&#x70B9;&#x7684;</span>
            <span class="hljs-keyword">if</span> index == <span class="hljs-keyword">None</span> <span class="hljs-keyword">and</span> sequence[i] &gt; rootNum:
                <span class="hljs-comment">#&#x8FD9;&#x4E2A;&#x65F6;&#x5019;&#x5C31;&#x628A;&#x7D22;&#x5F15;&#x8D4B;&#x503C;&#x7ED9; index</span>
                index = i
            <span class="hljs-comment">#&#x5982;&#x679C;&#x8BF4;&#x7D22;&#x5F15;&#x4E0D;&#x7B49;&#x4E8E;&#x7A7A;&#x800C;&#x4E14;&#x6570;&#x7EC4;&#x7684;&#x503C;&#x90FD;&#x662F;&#x5C0F;&#x4E8E; &#x6839;&#x8282;&#x70B9;&#x7684;&#xFF0C;&#x90A3;&#x4E48;&#x5C31;&#x662F;&#x8BF4;&#x4E0D;&#x6EE1;&#x8DB3;&#x641C;&#x7D22;&#x4E8C;&#x53C9;&#x6811;&#x7684;&#x5B9A;&#x4E49;&#xFF0C;&#x90A3;&#x4E48;&#x5C31;&#x8FD4;&#x56DE;&#x5047;</span>
            <span class="hljs-keyword">if</span> index != <span class="hljs-keyword">None</span> <span class="hljs-keyword">and</span> sequence[i] &lt; rootNum:
                <span class="hljs-keyword">return</span> <span class="hljs-keyword">False</span>
        <span class="hljs-comment">#&#x5F97;&#x5230;&#x90A3;&#x4E2A;&#x5927;&#x4E8E;&#x6839;&#x8282;&#x70B9;&#x7684;&#x503C;&#x7684;&#x7D22;&#x5F15;&#x503C;&#x4EE5;&#x540E;&#xFF0C;&#x5224;&#x65AD;</span>
        <span class="hljs-comment">#&#x5982;&#x679C;&#x8BF4; &#x5B83;&#x7684; &#x540E;&#x5E8F;&#x904D;&#x5386;&#x7684;&#x6570;&#x7EC4;&#x4E2D;&#x524D;&#x534A;&#x90E8;&#x5206;&#x7B49;&#x4E8E;&#x7A7A;&#x7684;&#x8BDD;&#xFF0C;&#x90A3;&#x4E48;&#x5224;&#x65AD;&#x662F;&#x5426;&#x4E3A;&#x8FD9;&#x4E2A;&#x4E8C;&#x53C9;&#x641C;&#x7D22;&#x6811;&#x7684;&#x5DE6;&#x534A;&#x90E8;&#x5206;&#x5C31;&#x4E3A;&#x771F;&#x3002;</span>
        <span class="hljs-keyword">if</span> sequence[:index] == []:
            leftRet = <span class="hljs-keyword">True</span>
        <span class="hljs-comment">#&#x5982;&#x679C;&#x5DE6;&#x534A;&#x8FB9;&#x4E0D;&#x662F;&#x7A7A;&#x7684;&#x8BDD;&#xFF0C;&#x90A3;&#x4E48;&#x5C31;&#x4EE5;&#x5DE6;&#x534A;&#x8FB9;&#x4E3A;&#x4E00;&#x4E2A;&#x65B0;&#x7684;&#x904D;&#x5386;&#x5F97;&#x5230;&#x7684;&#x6570;&#x7EC4;&#xFF0C;&#x6765;&#x9012;&#x5F52;&#x5224;&#x65AD;&#x505A;&#x4E00;&#x4E2A;&#x5FAA;&#x73AF;</span>
        <span class="hljs-keyword">else</span>:
            leftRet = self.VerifySquenceOfBST(sequence[:index])
        <span class="hljs-comment">#&#x5F97;&#x5230;&#x90A3;&#x4E2A;&#x5927;&#x4E8E;&#x6839;&#x8282;&#x70B9;&#x7684;&#x503C;&#x7684;&#x7D22;&#x5F15;&#x503C;&#x4EE5;&#x540E;&#xFF0C;&#x5224;&#x65AD;</span>
        <span class="hljs-comment">#&#x5982;&#x679C;&#x8BF4; &#x5B83;&#x7684; &#x540E;&#x5E8F;&#x904D;&#x5386;&#x7684;&#x6570;&#x7EC4;&#x4E2D;&#x540E;&#x534A;&#x90E8;&#x5206;&#x7B49;&#x4E8E;&#x7A7A;&#x7684;&#x8BDD;&#xFF0C;&#x90A3;&#x4E48;&#x5224;&#x65AD;&#x662F;&#x5426;&#x4E3A;&#x8FD9;&#x4E2A;&#x4E8C;&#x53C9;&#x641C;&#x7D22;&#x6811;&#x7684;&#x53F3;&#x534A;&#x90E8;&#x5206;&#x5C31;&#x4E3A;&#x771F;&#x3002;</span>
        <span class="hljs-keyword">if</span> sequence[index:] == []:
            rightRet = <span class="hljs-keyword">True</span>
        <span class="hljs-keyword">else</span>:
            <span class="hljs-comment">#&#x5982;&#x679C;&#x53F3;&#x534A;&#x8FB9;&#x4E0D;&#x662F;&#x7A7A;&#x7684;&#x8BDD;&#xFF0C;&#x90A3;&#x4E48;&#x5C31;&#x4EE5;&#x53F3;&#x534A;&#x8FB9;&#x4E3A;&#x4E00;&#x4E2A;&#x65B0;&#x7684;&#x904D;&#x5386;&#x5F97;&#x5230;&#x7684;&#x6570;&#x7EC4;&#xFF0C;&#x6765;&#x9012;&#x5F52;&#x5224;&#x65AD;&#x505A;&#x4E00;&#x4E2A;&#x5FAA;&#x73AF;</span>
            rightRet = self.VerifySquenceOfBST(sequence[index:])
        <span class="hljs-comment">#&#x6700;&#x540E;&#x8FD4;&#x56DE; &#x5982;&#x679C;&#x4E24;&#x8FB9;&#x5224;&#x65AD;&#x90FD;&#x662F;&#x771F;&#x7684;&#x8BDD;&#x90A3;&#x4E48;&#x8FD9;&#x4E2A;&#x540E;&#x5E8F;&#x904D;&#x5386;&#x5C31;&#x662F;&#x8FD9;&#x4E2A;&#x4E8C;&#x53C9;&#x641C;&#x7D22;&#x6811;&#x7684;&#x540E;&#x5E8F;&#x904D;&#x5386;&#x3002;</span>
        <span class="hljs-keyword">return</span> leftRet <span class="hljs-keyword">and</span> rightRet
</code></pre>
<hr>
<h2 id="30&#x4E8C;&#x53C9;&#x6811;&#x4E2D;&#x548C;&#x4E3A;&#x67D0;&#x4E00;&#x503C;&#x7684;&#x8DEF;&#x5F84;">30.&#x4E8C;&#x53C9;&#x6811;&#x4E2D;&#x548C;&#x4E3A;&#x67D0;&#x4E00;&#x503C;&#x7684;&#x8DEF;&#x5F84;</h2>
<p><strong>&#x8F93;&#x5165;&#x4E00;&#x9897;&#x4E8C;&#x53C9;&#x6811;&#x7684;&#x8DDF;&#x8282;&#x70B9;&#x548C;&#x4E00;&#x4E2A;&#x6574;&#x6570;&#xFF0C;&#x6253;&#x5370;&#x51FA;&#x4E8C;&#x53C9;&#x6811;&#x4E2D;&#x7ED3;&#x70B9;&#x503C;&#x7684;&#x548C;&#x4E3A;&#x8F93;&#x5165;&#x6574;&#x6570;&#x7684;&#x6240;&#x6709;&#x8DEF;&#x5F84;&#x3002;&#x8DEF;&#x5F84;&#x5B9A;&#x4E49;&#x4E3A;&#x4ECE;&#x6811;&#x7684;&#x6839;&#x7ED3;&#x70B9;&#x5F00;&#x59CB;&#x5F80;&#x4E0B;&#x4E00;&#x76F4;&#x5230;&#x53F6;&#x7ED3;&#x70B9;&#x6240;&#x7ECF;&#x8FC7;&#x7684;&#x7ED3;&#x70B9;&#x5F62;&#x6210;&#x4E00;&#x6761;&#x8DEF;&#x5F84;&#x3002;(&#x6CE8;&#x610F;: &#x5728;&#x8FD4;&#x56DE;&#x503C;&#x7684;list&#x4E2D;&#xFF0C;&#x6570;&#x7EC4;&#x957F;&#x5EA6;&#x5927;&#x7684;&#x6570;&#x7EC4;&#x9760;&#x524D;)</strong></p>
<p>&#x601D;&#x8DEF;&#xFF1A;&#x5728;&#x6811;&#x7684;&#x524D;&#x5E8F;&#xFF0C;&#x4E2D;&#x5E8F;&#xFF0C;&#x540E;&#x5E8F;&#x904D;&#x5386;&#x4E09;&#x79CD;&#x904D;&#x5386;&#x65B9;&#x5F0F;&#x4E2D;&#xFF0C;&#x53EA;&#x6709;&#x524D;&#x5E8F;&#x904D;&#x5386;&#x662F;&#x9996;&#x5148;&#x8BBF;&#x95EE;&#x6839;&#x8282;&#x70B9;&#x7684;&#xFF0C;&#x6240;&#x4EE5;&#x6211;&#x4EEC;&#x9700;&#x8981;&#x7528;&#x5230;&#x524D;&#x5E8F;&#x904D;&#x5386;&#xFF0C;&#x5F53;&#x6211;&#x4EEC;&#x7528;&#x524D;&#x5E8F;&#x904D;&#x5386;&#x8BBF;&#x95EE;&#x5230;&#x67D0;&#x4E00;&#x4E2A;&#x53F6;&#x5B50;&#x8282;&#x70B9;&#x7684;&#x65F6;&#x5019;&#xFF0C;&#x6211;&#x4EEC;&#x628A;&#x8BE5;&#x8282;&#x70B9;&#x6DFB;&#x52A0;&#x5230;&#x8DEF;&#x5F84;&#x4E0A;&#xFF0C;&#x5E76;&#x7D2F;&#x52A0;&#x8BE5;&#x8282;&#x70B9;&#x7684;&#x503C;&#xFF0C;&#x5982;&#x679C;&#x8BE5;&#x8282;&#x70B9;&#x4E3A;&#x53F6;&#x8282;&#x70B9;&#xFF0C;&#x5E76;&#x4E14;&#x8DEF;&#x5F84;&#x4E2D;&#x8282;&#x70B9;&#x503C;&#x521A;&#x597D;&#x7B49;&#x4E8E;&#x8F93;&#x5165;&#x7684;&#x6574;&#x6570;&#xFF0C;&#x5219;&#x5F53;&#x524D;&#x7684;&#x8DEF;&#x5F84;&#x7B26;&#x5408;&#x8981;&#x6C42;&#xFF0C;&#x6211;&#x4EEC;&#x628A;&#x5B83;&#x6253;&#x5370;&#x51FA;&#x6765;&#xFF0C;&#x5982;&#x679C;&#x5F53;&#x524D;&#x7684;&#x7ED3;&#x70B9;&#x4E0D;&#x662F;&#x53F6;&#x5B50;&#x8282;&#x70B9;&#xFF0C;&#x5219;&#x7EE7;&#x7EED;&#x8BBF;&#x95EE;&#x5B83;&#x7684;&#x5B50;&#x8282;&#x70B9;&#x3002;&#x5F53;&#x524D;&#x8282;&#x70B9;&#x8BBF;&#x95EE;&#x7ED3;&#x675F;&#x540E;&#xFF0C;&#x9012;&#x5F52;&#x51FD;&#x6570;&#x5C06;&#x81EA;&#x52A8;&#x56DE;&#x5230;&#x5B83;&#x7684;&#x7236;&#x8282;&#x70B9;&#x3002;&#x56E0;&#x6B64;&#x6211;&#x4EEC;&#x5728;&#x51FD;&#x6570;&#x9000;&#x51FA;&#x4E4B;&#x524D;&#x8981;&#x5728;&#x8DEF;&#x5F84;&#x4E0A;&#x5220;&#x9664;&#x5F53;&#x524D;&#x7684;&#x7ED3;&#x70B9;&#x5E76;&#x51CF;&#x53BB;&#x5F53;&#x524D;&#x7ED3;&#x70B9;&#x7684;&#x503C;&#xFF0C;&#x4EE5;&#x786E;&#x4FDD;&#x8FD4;&#x56DE;&#x7236;&#x8282;&#x70B9;&#x65F6;&#x8DEF;&#x5F84;&#x521A;&#x597D;&#x662F;&#x4ECE;&#x6839;&#x8282;&#x70B9;&#x5230;&#x7236;&#x8282;&#x70B9;&#x3002;</p>
<pre><code class="lang-python"><span class="hljs-string">&quot;&quot;&quot;
&#x9012;&#x5F52;&#x5148;&#x5E8F;&#x904D;&#x5386;&#x6811;&#xFF0C; &#x628A;&#x7ED3;&#x70B9;&#x52A0;&#x5165;&#x8DEF;&#x5F84;&#x3002;
&#x82E5;&#x8BE5;&#x7ED3;&#x70B9;&#x662F;&#x53F6;&#x5B50;&#x7ED3;&#x70B9;&#x5219;&#x6BD4;&#x8F83;&#x5F53;&#x524D;&#x8DEF;&#x5F84;&#x548C;&#x662F;&#x5426;&#x7B49;&#x4E8E;&#x671F;&#x5F85;&#x548C;&#x3002;
&#x5F39;&#x51FA;&#x7ED3;&#x70B9;&#xFF0C;&#x6BCF;&#x4E00;&#x8F6E;&#x9012;&#x5F52;&#x8FD4;&#x56DE;&#x5230;&#x7236;&#x7ED3;&#x70B9;&#x65F6;&#xFF0C;&#x5F53;&#x524D;&#x8DEF;&#x5F84;&#x4E5F;&#x5E94;&#x8BE5;&#x56DE;&#x9000;&#x4E00;&#x4E2A;&#x7ED3;&#x70B9;

&quot;&quot;&quot;</span>
<span class="hljs-comment"># -*- coding:utf-8 -*-</span>
<span class="hljs-comment"># class TreeNode:</span>
<span class="hljs-comment">#     def __init__(self, x):</span>
<span class="hljs-comment">#         self.val = x</span>
<span class="hljs-comment">#         self.left = None</span>
<span class="hljs-comment">#         self.right = None</span>
<span class="hljs-keyword">import</span> copy


<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-comment"># &#x8FD4;&#x56DE;&#x4E8C;&#x7EF4;&#x5217;&#x8868;&#xFF0C;&#x5185;&#x90E8;&#x6BCF;&#x4E2A;&#x5217;&#x8868;&#x8868;&#x793A;&#x627E;&#x5230;&#x7684;&#x8DEF;&#x5F84;</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">FindPath</span><span class="hljs-params">(self, root, expectNumber)</span>:</span>
        <span class="hljs-comment"># write code here</span>
        <span class="hljs-comment">#&#x5224;&#x65AD;&#x5982;&#x679C; &#x6839;&#x8282;&#x70B9;&#x4E3A;&#x7A7A;&#x7684;&#x8BDD;&#x90A3;&#x4E48;&#x6CA1;&#x6709;&#x6570;&#x636E;&#x4E3A;&#x7A7A;</span>
        <span class="hljs-keyword">if</span> root == <span class="hljs-keyword">None</span>:
            <span class="hljs-keyword">return</span> []
        <span class="hljs-comment">#&#x8FD4;&#x56DE;&#x7684;&#x5217;&#x8868;</span>
        ret = []
        <span class="hljs-comment">#&#x8F85;&#x52A9;&#x5217;&#x8868; &#x7B2C;&#x4E00;&#x4E2A;&#x503C;&#x4E3A; &#x6839;&#x8282;&#x70B9;</span>
        support = [root]
        <span class="hljs-comment">#&#x8F85;&#x52A9;&#x6570;&#x7EC4;  &#x7B2C;&#x4E00;&#x4E2A;  &#x4E3A;&#x6839;&#x8282;&#x70B9;&#x7684;&#x503C;</span>
        supportArrayList = [[root.val]]
        <span class="hljs-comment">#&#x5F53;&#x6211;&#x4EEC;&#x8F85;&#x52A9;&#x5217;&#x8868;&#x4E2D;&#x6709;&#x8282;&#x70B9;&#x7684;&#x65F6;&#x5019;</span>
        <span class="hljs-keyword">while</span> support:
            <span class="hljs-comment">#&#x4E34;&#x65F6;&#x7684;&#x7ED3;&#x70B9; &#x4E3A; &#x8F85;&#x52A9;&#x5217;&#x8868;&#x4E2D;&#x7684;&#x7B2C;&#x4E00;&#x4E2A;&#x7ED3;&#x70B9;</span>
            tmpNode = support[<span class="hljs-number">0</span>]
            <span class="hljs-comment">#&#x4E34;&#x65F6;&#x7684;&#x6570;&#x7EC4;  &#x4E3A; &#x8F85;&#x52A9;&#x6570;&#x7EC4;&#x4E2D;&#x7684;&#x7B2C;&#x4E00;&#x4E2A;&#x503C;</span>
            tmpArrayList = supportArrayList[<span class="hljs-number">0</span>]
            <span class="hljs-comment">#&#x5224;&#x65AD; &#x6211;&#x4EEC;&#x7684;&#x4E34;&#x65F6;&#x7ED3;&#x70B9;&#x7684;&#x5DE6;&#x8282;&#x70B9;&#x662F;&#x4E0D;&#x662F;&#x5B58;&#x5728;&#xFF0C;&#x800C;&#x4E14; &#x4E34;&#x65F6;&#x7ED3;&#x70B9;&#x7684;&#x53F3;&#x7ED3;&#x70B9;&#x662F;&#x4E0D;&#x662F;&#x5B58;&#x5728;&#xFF0C;&#x5982;&#x679C;&#x4E0D;&#x5B58;&#x5728;&#x7684;&#x8BDD;</span>
            <span class="hljs-keyword">if</span> tmpNode.left == <span class="hljs-keyword">None</span> <span class="hljs-keyword">and</span> tmpNode.right == <span class="hljs-keyword">None</span>:
                <span class="hljs-comment">#&#x5C31;&#x5224;&#x65AD;&#x6211;&#x4EEC;&#x73B0;&#x5728;&#x4E34;&#x65F6;&#x6570;&#x7EC4;&#x4E2D;&#x7684;&#x503C;&#x7684;&#x548C;&#x662F;&#x4E0D;&#x662F;&#x7B49;&#x4E8E;&#x8F93;&#x5165;&#x7684;&#x90A3;&#x4E2A;&#x6574;&#x6570;</span>
                <span class="hljs-keyword">if</span> sum(tmpArrayList) == expectNumber:
                    <span class="hljs-comment">#&#x5982;&#x679C;&#x7B49;&#x4E8E;&#x7684;&#x8BDD;&#xFF0C;&#x5C31;&#x628A;&#x8FD9;&#x4E2A;&#x4E34;&#x65F6;&#x7684;&#x8F85;&#x52A9;&#x6570;&#x7EC4;&#x63D2;&#x5165;&#x5230;&#x6211;&#x4EEC;&#x8FD4;&#x56DE;&#x7684;&#x6570;&#x7EC4;&#x4E2D;&#xFF0C;&#x8FD9;&#x5C31;&#x662F;&#x6211;&#x4EEC;&#x627E;&#x5230;&#x7684;&#x7B2C;&#x4E00;&#x4E2A;&#x6EE1;&#x8DB3;&#x6761;&#x4EF6;&#x7684;&#x8DEF;&#x5F84;&#xFF0C;&#x9898;&#x76EE;&#x8981;&#x6C42; &#x957F;&#x5EA6;&#x5927;&#x7684;&#x9760;&#x524D;&#xFF0C;&#x90A3;&#x4E48;&#x4E5F;&#x5C31;&#x662F;&#x8BF4;&#x8D8A;&#x5148;&#x63D2;&#x8FDB;&#x53BB;&#x8D8A;&#x9760;&#x540E;&#xFF0C;&#x6240;&#x4EE5;&#x6211;&#x4EEC;&#x7528;insert &#x7D22;&#x5F15;&#x63D2;&#x5165;&#x3002;</span>
                    ret.insert(<span class="hljs-number">0</span>, tmpArrayList)
            <span class="hljs-comment">#&#x5982;&#x679C;&#x6211;&#x4EEC;&#x4E34;&#x65F6;&#x7ED3;&#x70B9;&#x7684;&#x5DE6;&#x8282;&#x70B9;&#x5B58;&#x5728;</span>
            <span class="hljs-keyword">if</span> tmpNode.left:
                <span class="hljs-comment">#&#x5728;&#x6211;&#x4EEC;&#x8F85;&#x52A9;&#x5217;&#x8868;&#x4E2D;&#x6DFB;&#x52A0;&#x8FD9;&#x4E2A;&#x5DE6;&#x8282;&#x70B9;</span>
                support.append(tmpNode.left)
                <span class="hljs-comment">#&#x7136;&#x540E;&#x628A;&#x539F;&#x6765;&#x4E34;&#x65F6;&#x6570;&#x7EC4;&#x590D;&#x5236;&#x4E00;&#x4EFD;&#xFF0C;&#x4E3A;&#x65B0;&#x7684;&#x8F85;&#x52A9;&#x6570;&#x7EC4;&#xFF0C;&#x6765;&#x628A;&#x8FD9;&#x4E2A;&#x5DE6;&#x8282;&#x70B9;&#x7684;&#x503C;&#x63D2;&#x5165;&#x5230;&#x6211;&#x4EEC;&#x7684;&#x65B0;&#x4E34;&#x65F6;&#x8F85;&#x52A9;&#x6570;&#x7EC4;&#x4E2D;&#xFF0C;&#x5728;&#x8F85;&#x52A9;&#x6570;&#x7EC4;&#x4E2D;&#x6DFB;&#x52A0;&#x8FD9;&#x4E2A;&#x65B0;&#x7684;&#x4E34;&#x65F6;&#x6570;&#x7EC4;</span>
                newTmpArrayList = copy.copy(tmpArrayList)
                newTmpArrayList.append(tmpNode.left.val)
                supportArrayList.append(newTmpArrayList)
            <span class="hljs-comment">#&#x5982;&#x679C;&#x6211;&#x4EEC;&#x4E34;&#x65F6;&#x7ED3;&#x70B9;&#x7684;&#x53F3;&#x7ED3;&#x70B9;&#x5B58;&#x5728;&#x7684;&#x8BDD;</span>
            <span class="hljs-keyword">if</span> tmpNode.right:
                <span class="hljs-comment">#&#x6B65;&#x9AA4;&#x540C;&#x4E0A;&#xFF0C;&#x628A;&#x53F3;&#x7ED3;&#x70B9;&#x6DFB;&#x52A0;&#x5230;&#x8F85;&#x52A9;&#x5217;&#x8868;&#x4E2D;</span>
                support.append(tmpNode.right)
                <span class="hljs-comment">#&#x628A;&#x539F;&#x6765;&#x7684;&#x4E34;&#x65F6;&#x8F85;&#x52A9;&#x6570;&#x7EC4; &#x590D;&#x5236;&#x4E00;&#x4EFD;&#x7ED9; &#x65B0;&#x7684;&#x8F85;&#x52A9;&#x6570;&#x7EC4;</span>
                newTmpArrayList = copy.copy(tmpArrayList)
                <span class="hljs-comment">#&#x7136;&#x540E; &#x628A; &#x4E34;&#x65F6;&#x7ED3;&#x70B9;&#x7684;&#x53F3;&#x7ED3;&#x70B9;&#x7684;&#x503C;&#x6DFB;&#x52A0;&#x5230; &#x6211;&#x4EEC;&#x65B0;&#x7684;&#x4E34;&#x65F6;&#x8F85;&#x52A9;&#x6570;&#x7EC4;&#x4E2D;</span>
                newTmpArrayList.append(tmpNode.right.val)
                <span class="hljs-comment">#&#x5728;&#x8F85;&#x52A9;&#x6570;&#x7EC4;&#x4E2D;&#x6DFB;&#x52A0;&#x8FD9;&#x4E2A;&#x65B0;&#x7684;&#x4E34;&#x65F6;&#x8F85;&#x52A9;&#x6570;&#x7EC4;</span>
                supportArrayList.append(newTmpArrayList)
            <span class="hljs-comment">#&#x5220;&#x9664;&#x8F85;&#x52A9;&#x6570;&#x7EC4;&#x4E2D;&#x7684;&#x7B2C;&#x4E00;&#x4E2A;&#x503C;</span>
            <span class="hljs-keyword">del</span> supportArrayList[<span class="hljs-number">0</span>]
            <span class="hljs-comment">#&#x5220;&#x9664;&#x8F85;&#x52A9;&#x5217;&#x8868;&#x7684;&#x7B2C;&#x4E00;&#x4E2A;&#x503C;</span>
            <span class="hljs-keyword">del</span> support[<span class="hljs-number">0</span>]
        <span class="hljs-comment">#&#x8FD4;&#x56DE;&#x6211;&#x4EEC;&#x63D2;&#x5165;&#x7684;&#x6EE1;&#x8DB3;&#x9898;&#x76EE;&#x7684; &#x548C;&#x4E3A;&#x67D0;&#x4E00;&#x503C;&#x7684;&#x8DEF;&#x5F84;&#x7684;&#x8FD4;&#x56DE;&#x7684;&#x5217;&#x8868;</span>
        <span class="hljs-keyword">return</span> ret

<span class="hljs-comment">#&#x9488;&#x5BF9;&#x4E0A;&#x9762;&#x601D;&#x8DEF;&#x7684;&#x4EE3;&#x7801;&#xFF1A;</span>

<span class="hljs-comment"># -*- coding:utf-8 -*-</span>
<span class="hljs-comment"># class TreeNode:</span>
<span class="hljs-comment">#     def __init__(self, x):</span>
<span class="hljs-comment">#         self.val = x</span>
<span class="hljs-comment">#         self.left = None</span>
<span class="hljs-comment">#         self.right = None</span>
<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution2</span>:</span>
    <span class="hljs-comment"># &#x8FD4;&#x56DE;&#x4E8C;&#x7EF4;&#x5217;&#x8868;&#xFF0C;&#x5185;&#x90E8;&#x6BCF;&#x4E2A;&#x5217;&#x8868;&#x8868;&#x793A;&#x627E;&#x5230;&#x7684;&#x8DEF;&#x5F84;</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">FindPath</span><span class="hljs-params">(self, root, expectNumber)</span>:</span>
        <span class="hljs-comment"># write code here</span>
        <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> root:
            <span class="hljs-keyword">return</span> []

        result = []

        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">FindPathMain</span><span class="hljs-params">(root, path, currentSum)</span>:</span>
            currentSum += root.val

            path.append(root)
            isLeaf = root.left == <span class="hljs-keyword">None</span> <span class="hljs-keyword">and</span> root.right == <span class="hljs-keyword">None</span>

            <span class="hljs-keyword">if</span> currentSum == expectNumber <span class="hljs-keyword">and</span> isLeaf:
                onePath = []
                <span class="hljs-keyword">for</span> node <span class="hljs-keyword">in</span> path:
                    onePath.append(node.val)
                result.append(onePath)

            <span class="hljs-keyword">if</span> currentSum &lt; expectNumber:
                <span class="hljs-keyword">if</span> root.left:
                    FindPathMain(root.left, path, currentSum)
                <span class="hljs-keyword">if</span> root.right:
                    FindPathMain(root.right, path, currentSum)

            path.pop()

        FindPathMain(root, [], <span class="hljs-number">0</span>)

        <span class="hljs-keyword">return</span> result
</code></pre>
<hr>
<h2 id="31&#x4E8C;&#x53C9;&#x641C;&#x7D22;&#x6811;&#x4E0E;&#x53CC;&#x5411;&#x94FE;&#x8868;">31.&#x4E8C;&#x53C9;&#x641C;&#x7D22;&#x6811;&#x4E0E;&#x53CC;&#x5411;&#x94FE;&#x8868;</h2>
<p><strong>&#x8F93;&#x5165;&#x4E00;&#x68F5;&#x4E8C;&#x53C9;&#x641C;&#x7D22;&#x6811;&#xFF0C;&#x5C06;&#x8BE5;&#x4E8C;&#x53C9;&#x641C;&#x7D22;&#x6811;&#x8F6C;&#x6362;&#x6210;&#x4E00;&#x4E2A;&#x6392;&#x5E8F;&#x7684;&#x53CC;&#x5411;&#x94FE;&#x8868;&#x3002;&#x8981;&#x6C42;&#x4E0D;&#x80FD;&#x521B;&#x5EFA;&#x4EFB;&#x4F55;&#x65B0;&#x7684;&#x7ED3;&#x70B9;&#xFF0C;&#x53EA;&#x80FD;&#x8C03;&#x6574;&#x6811;&#x4E2D;&#x7ED3;&#x70B9;&#x6307;&#x9488;&#x7684;&#x6307;&#x5411;&#x3002;</strong></p>
<p>&#x5728;&#x4E8C;&#x53C9;&#x6811;&#x4E2D;&#x6BCF;&#x4E2A;&#x7ED3;&#x70B9;&#x90FD;&#x6709;&#x4E24;&#x4E2A;&#x6307;&#x5411;&#x5B50;&#x8282;&#x70B9;&#x7684;&#x6307;&#x9488;&#xFF0C;&#x5728;&#x53CC;&#x5411;&#x94FE;&#x8868;&#x4E2D;&#x4E5F;&#x662F;&#x6709;&#x4E24;&#x4E2A;&#x6307;&#x9488;&#xFF0C;&#x5206;&#x522B;&#x6307;&#x5411;&#x524D;&#x4E00;&#x4E2A;&#x7ED3;&#x70B9;&#x548C;&#x540E;&#x4E00;&#x4E2A;&#x7ED3;&#x70B9;&#x3002;</p>
<p>&#x6839;&#x8282;&#x70B9; &#x5DE6;&#x6307;&#x9488;&#x8981;&#x94FE;&#x5728; &#x5DE6;&#x5B50;&#x6811;&#x7684;&#x6700;&#x53F3;&#x8FB9;&#xFF0C;&#x6839;&#x8282;&#x70B9;&#x7684;&#x53F3;&#x6307;&#x9488;&#x8981;&#x94FE;&#x5728;&#x53F3;&#x5B50;&#x6811;&#x7684;&#x6700;&#x5DE6;&#x8FB9;&#x3002;</p>
<p>&#x6392;&#x5E8F;&#x7684;&#xFF0C;&#x6839;&#x8282;&#x70B9;&#x548C; &#x5DE6;&#x5B50;&#x6811;&#x4E2D;&#x6700;&#x5927;&#x7684;&#x94FE;&#xFF0C;&#x548C;&#x53F3;&#x5B50;&#x6811;&#x6700;&#x5C0F;&#x7684;&#x94FE;&#x3002;</p>
<p>&#x90A3;&#x4E48;&#x628A;&#x6BCF;&#x4E00;&#x4E2A;&#x7ED3;&#x70B9;&#x90FD;&#x5F53;&#x505A;&#x4E00;&#x4E2A;&#x6839;&#x8282;&#x70B9;&#x6765;&#x9012;&#x5F52;&#xFF0C;&#x90A3;&#x4E48;&#x5C31;&#x662F;&#x5728;&#x5FAA;&#x73AF;&#x505A;&#x4E0A;&#x9762;&#x7684;&#x64CD;&#x4F5C;&#x3002;</p>
<p>&#x5BF9;&#x4E8E;&#x6574;&#x4E2A;&#x94FE;&#x8868;&#x6765;&#x8BF4;&#xFF0C;&#x6211;&#x4EEC;&#x8981;&#x8F93;&#x51FA;&#x6700;&#x5DE6;&#x7ED3;&#x70B9;&#x3002;</p>
<pre><code class="lang-python"><span class="hljs-comment"># -*- coding:utf-8 -*-</span>
<span class="hljs-comment"># class TreeNode:</span>
<span class="hljs-comment">#     def __init__(self, x):</span>
<span class="hljs-comment">#         self.val = x</span>
<span class="hljs-comment">#         self.left = None</span>
<span class="hljs-comment">#         self.right = None</span>
<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">Convert</span><span class="hljs-params">(self, pRootOfTree)</span>:</span>
        <span class="hljs-comment"># write code here</span>
        <span class="hljs-comment">#&#x9996;&#x5148;&#x5224;&#x65AD;&#x7ED9;&#x7684;&#x4E8C;&#x53C9;&#x6811;&#x662F;&#x4E0D;&#x662F;&#x7A7A;&#x7684;&#xFF0C;&#x5982;&#x679C;&#x662F;&#x7A7A;&#x7684;&#x5C31;&#x8FD4;&#x56DE;&#x7A7A;</span>
        <span class="hljs-keyword">if</span> pRootOfTree == <span class="hljs-keyword">None</span>
            <span class="hljs-keyword">return</span> <span class="hljs-keyword">None</span>
        <span class="hljs-comment">#&#x627E;&#x53F3;&#x7ED3;&#x70B9; &#x53F3;&#x5B50;&#x6811;</span>
        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">find_right</span><span class="hljs-params">(node)</span>:</span>
            <span class="hljs-keyword">while</span> node.right:
                node = node.right
            <span class="hljs-keyword">return</span> node
        <span class="hljs-comment">#&#x9012;&#x5F52; &#x5904;&#x7406;&#x5DE6;&#x8282;&#x70B9;&#xFF0C;&#x5E76;&#x8FD4;&#x56DE;&#x5DE6;&#x5B50;&#x6811; &#x6700;&#x5DE6;&#x8FB9;&#x7684;&#x7ED3;&#x70B9;</span>
        leftNode = self.Convert(pRootOfTree.left)
        <span class="hljs-comment">#&#x9012;&#x5F52;&#x5904;&#x7406;&#x53F3;&#x7ED3;&#x70B9;&#xFF0C;&#x5E76;&#x8FD4;&#x56DE;&#x53F3;&#x5B50;&#x6811;&#x6700;&#x5DE6;&#x8FB9;&#x7684;&#x7ED3;&#x70B9;</span>
        rightNode = self.Convert(pRootOfTree.right)
        <span class="hljs-comment">#&#x5C06;&#x8FD4;&#x56DE;&#x7684;&#x5DE6;&#x5B50;&#x6811;&#x7684;&#x5DE6;&#x8282;&#x70B9;&#x8D4B;&#x503C;&#x7ED9;&#x8FD4;&#x56DE;&#x7684;&#x7ED3;&#x70B9; &#x4FDD;&#x5B58;&#x4F4F;&#xFF0C;&#x56E0;&#x4E3A;&#x4E48;&#x6700;&#x540E;&#x8981;&#x8FD4;&#x56DE;&#x8FD9;&#x4E2A;&#x3002;</span>
        retNode = leftNode
        <span class="hljs-comment">#&#x5982;&#x679C;&#x8F93;&#x51FA;&#x7684;&#x5DE6;&#x8282;&#x70B9;&#x5B58;&#x5728;</span>
        <span class="hljs-keyword">if</span> leftNode:
            <span class="hljs-comment">#&#x90A3;&#x4E48;&#x6211;&#x4EEC;&#x5C31;&#x8981;&#x53BB;&#x5BFB;&#x627E;&#x5B83;&#x7684;&#x53F3;&#x7ED3;&#x70B9;&#xFF0C;&#x4E00;&#x76F4;&#x627E;&#xFF0C;&#x627E;&#x5230;&#x6700;&#x53F3;&#x7684;&#xFF0C;&#x4EE5;&#x4FBF;&#x540E;&#x9762;&#x6211;&#x4EEC;&#x8981;&#x4ED6;&#x8DDF;&#x6839;&#x8282;&#x70B9;&#x76F8;&#x94FE;&#x63A5;&#x4E0A;</span>
            <span class="hljs-comment">#&#x628A;&#x6700;&#x53F3;&#x7684;&#x8FD9;&#x4E2A;&#x7ED3;&#x70B9; &#x8D4B;&#x503C; &#x7ED9; &#x5DE6;&#x8282;&#x70B9;</span>
            leftNode = find_right(leftNode)
        <span class="hljs-keyword">else</span>:
            <span class="hljs-comment">#&#x5982;&#x679C;&#x6CA1;&#x6709;&#x5DE6;&#x8282;&#x70B9;&#x5B58;&#x5728;&#x7684;&#x8BDD;&#xFF0C;&#x90A3;&#x4E48;&#x628A;&#x6839;&#x8282;&#x70B9;&#x7684;&#x503C;&#x7ED9;&#x8FD9;&#x4E2A;&#x8FD4;&#x56DE;&#x7684;&#x7ED3;&#x70B9;</span>
            retNode = pRootOfTree

        <span class="hljs-comment">#&#x6839;&#x8282;&#x70B9;&#x7684;&#x5DE6;&#x8282;&#x70B9; &#x4E0E; &#x4E0A;&#x9762;&#x6211;&#x4EEC;&#x627E;&#x53F3;&#x7ED3;&#x70B9; &#x627E;&#x5230;&#x7684; &#x90A3;&#x4E2A; &#x6700;&#x53F3;&#x7684;&#x7ED3;&#x70B9;&#x8D4B;&#x503C;&#x7ED9; &#x5DE6;&#x8282;&#x70B9; &#x7684;&#x7ED3;&#x70B9; &#x76F8; &#x94FE;&#x63A5; &#x4E0A;</span>
        pRootOfTree.left = leftNode
        <span class="hljs-comment">#&#x6839;&#x8282;&#x70B9;&#x7684;&#x53F3;&#x7ED3;&#x70B9;&#xFF0C;&#x662F;&#x4E0A;&#x9762;&#x8FD4;&#x56DE;&#x56DE;&#x6765;&#x7684;&#x53F3;&#x90E8;&#x5206;&#x7684; &#x6700;&#x5DE6;&#x7684;&#x4E00;&#x4E2A;</span>
        pRootOfTree.right = rightNode

        <span class="hljs-comment">#&#x5982;&#x679C;&#x5DE6;&#x8282;&#x70B9;&#x4E0D;&#x4E3A;&#x7A7A;&#x7684;&#x8BDD;</span>
        <span class="hljs-keyword">if</span> leftNode != <span class="hljs-keyword">None</span>:
            <span class="hljs-comment">#&#x90A3;&#x4E48;&#x5DE6;&#x5B50;&#x6811;&#x6700;&#x53F3;&#x8FB9;&#x7684;&#x7ED3;&#x70B9;&#x7684;&#x53F3;&#x6307;&#x9488;&#x6307;&#x5411;&#x6839;&#x8282;&#x70B9;</span>
            leftNode.right = pRootOfTree
         <span class="hljs-comment">#&#x5982;&#x679C;&#x53F3;&#x7ED3;&#x70B9;&#x4E0D;&#x4E3A;&#x7A7A;</span>
        <span class="hljs-keyword">if</span> rightNode != <span class="hljs-keyword">None</span>:
            <span class="hljs-comment">#&#x90A3;&#x4E48;&#x53F3;&#x5B50;&#x6811;&#x6700;&#x5DE6;&#x8FB9;&#x7684;&#x5DE6;&#x6307;&#x9488;&#x6307;&#x5411;&#x6839;&#x8282;&#x70B9;</span>
            rightNode.left = pRootOfTree
        <span class="hljs-comment">#&#x6700;&#x540E;&#x8FD4;&#x56DE;&#x8FD9;&#x4E2A; &#x6700;&#x5DE6;&#x7684;&#x7ED3;&#x70B9;</span>
        <span class="hljs-keyword">return</span> retNode
</code></pre>
<hr>
<h2 id="32&#x6700;&#x5C0F;&#x7684;k&#x4E2A;&#x6570;">32.&#x6700;&#x5C0F;&#x7684;k&#x4E2A;&#x6570;</h2>
<p><strong>&#x8F93;&#x5165;n&#x4E2A;&#x6574;&#x6570;&#xFF0C;&#x627E;&#x51FA;&#x5176;&#x4E2D;&#x6700;&#x5C0F;&#x7684;K&#x4E2A;&#x6570;&#x3002;&#x4F8B;&#x5982;&#x8F93;&#x5165;4,5,1,6,2,7,3,8&#x8FD9;8&#x4E2A;&#x6570;&#x5B57;&#xFF0C;&#x5219;&#x6700;&#x5C0F;&#x7684;4&#x4E2A;&#x6570;&#x5B57;&#x662F;1,2,3,4,&#x3002;</strong></p>
<pre><code class="lang-python"><span class="hljs-comment"># -*- coding:utf-8 -*-</span>
<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">GetLeastNumbers_Solution</span><span class="hljs-params">(self, tinput, k)</span>:</span>
        <span class="hljs-comment"># write code here</span>
        <span class="hljs-comment"># &#x6700;&#x5927;&#x5806;</span>

        <span class="hljs-comment"># &#x521B;&#x5EFA;&#x6216;&#x8005;&#x63D2;&#x5165;&#x6700;&#x5927;&#x5806;</span>
        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">createMaxHeap</span><span class="hljs-params">(num)</span>:</span>
            maxHeap.append(num)
            currentIndex = len(maxHeap) - <span class="hljs-number">1</span>
            <span class="hljs-keyword">while</span> currentIndex != <span class="hljs-number">0</span>:
                parentIndex = (currentIndex - <span class="hljs-number">1</span>) &gt;&gt; <span class="hljs-number">1</span>
                <span class="hljs-keyword">if</span> maxHeap[parentIndex] &lt; maxHeap[currentIndex]:
                    <span class="hljs-comment"># &#x4EA4;&#x6362;&#x4F4D;&#x7F6E;</span>
                    maxHeap[parentIndex], maxHeap[currentIndex] = maxHeap[currentIndex], maxHeap[parentIndex]
                <span class="hljs-keyword">else</span>:
                    <span class="hljs-keyword">break</span>

        <span class="hljs-comment"># &#x8C03;&#x6574;&#x6700;&#x5927;&#x5806;&#xFF0C;&#x5934;&#x7ED3;&#x70B9;&#x53D1;&#x751F;&#x6539;&#x53D8;</span>
        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">adjustMaxHeap</span><span class="hljs-params">(num)</span>:</span>
            <span class="hljs-keyword">if</span> num &lt; maxHeap[<span class="hljs-number">0</span>]:
                maxHeap[<span class="hljs-number">0</span>] = num
            maxHeapLen = len(maxHeap)
            index = <span class="hljs-number">0</span>
            <span class="hljs-keyword">while</span> index &lt; maxHeapLen:
                leftIndex = index * <span class="hljs-number">2</span> + <span class="hljs-number">1</span>
                rightIndex = index * <span class="hljs-number">2</span> + <span class="hljs-number">2</span>
                largerIndex = <span class="hljs-number">0</span>
                <span class="hljs-keyword">if</span> rightIndex &lt; maxHeapLen:
                    <span class="hljs-keyword">if</span> maxHeap[rightIndex] &lt; maxHeap[leftIndex]:
                        largerIndex = leftIndex
                    <span class="hljs-keyword">else</span>:
                        largerIndex = rightIndex
                <span class="hljs-keyword">elif</span> leftIndex &lt; maxHeapLen:
                    largerIndex = leftIndex
                <span class="hljs-keyword">else</span>:
                    <span class="hljs-keyword">break</span>
                <span class="hljs-keyword">if</span> maxHeap[index] &lt; maxHeap[largerIndex]:
                    maxHeap[index], maxHeap[largerIndex] = maxHeap[largerIndex], maxHeap[index]
                index = largerIndex

        maxHeap = []
        inputLen = len(tinput)
        <span class="hljs-keyword">if</span> inputLen &lt; k <span class="hljs-keyword">or</span> k &lt;= <span class="hljs-number">0</span>:
            <span class="hljs-keyword">return</span> []
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(inputLen):
            <span class="hljs-keyword">if</span> i &lt; k:
                createMaxHeap(tinput[i])
            <span class="hljs-keyword">else</span>:
                adjustMaxHeap(tinput[i])
        maxHeap.sort()
        <span class="hljs-keyword">return</span> maxHeap
</code></pre>
<hr>
<pre><code class="lang-python"><span class="hljs-comment"># -*- coding:utf-8 -*-</span>
<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">GetLeastNumbers_Solution</span><span class="hljs-params">(self, tinput, k)</span>:</span>
        <span class="hljs-comment"># write code here</span>
        <span class="hljs-keyword">if</span> tinput == [] <span class="hljs-keyword">or</span> k &gt; len(tinput):
            <span class="hljs-keyword">return</span> []
        tinput.sort()
        <span class="hljs-keyword">return</span> tinput[: k]
</code></pre>
<h2 id="33&#x6570;&#x636E;&#x6D41;&#x4E2D;&#x7684;&#x4E2D;&#x4F4D;&#x6570;">33.&#x6570;&#x636E;&#x6D41;&#x4E2D;&#x7684;&#x4E2D;&#x4F4D;&#x6570;</h2>
<p><strong>&#x5982;&#x4F55;&#x5F97;&#x5230;&#x4E00;&#x4E2A;&#x6570;&#x636E;&#x6D41;&#x4E2D;&#x7684;&#x4E2D;&#x4F4D;&#x6570;&#xFF1F;&#x5982;&#x679C;&#x4ECE;&#x6570;&#x636E;&#x6D41;&#x4E2D;&#x8BFB;&#x51FA;&#x5947;&#x6570;&#x4E2A;&#x6570;&#x503C;&#xFF0C;&#x90A3;&#x4E48;&#x4E2D;&#x4F4D;&#x6570;&#x5C31;&#x662F;&#x6240;&#x6709;&#x6570;&#x503C;&#x6392;&#x5E8F;&#x4E4B;&#x540E;&#x4F4D;&#x4E8E;&#x4E2D;&#x95F4;&#x7684;&#x6570;&#x503C;&#x3002;&#x5982;&#x679C;&#x4ECE;&#x6570;&#x636E;&#x6D41;&#x4E2D;&#x8BFB;&#x51FA;&#x5076;&#x6570;&#x4E2A;&#x6570;&#x503C;&#xFF0C;&#x90A3;&#x4E48;&#x4E2D;&#x4F4D;&#x6570;&#x5C31;&#x662F;&#x6240;&#x6709;&#x6570;&#x503C;&#x6392;&#x5E8F;&#x4E4B;&#x540E;&#x4E2D;&#x95F4;&#x4E24;&#x4E2A;&#x6570;&#x7684;&#x5E73;&#x5747;&#x503C;&#x3002;&#x6211;&#x4EEC;&#x4F7F;&#x7528;Insert()&#x65B9;&#x6CD5;&#x8BFB;&#x53D6;&#x6570;&#x636E;&#x6D41;&#xFF0C;&#x4F7F;&#x7528;<code>GetMedian()</code>&#x65B9;&#x6CD5;&#x83B7;&#x53D6;&#x5F53;&#x524D;&#x8BFB;&#x53D6;&#x6570;&#x636E;&#x7684;&#x4E2D;&#x4F4D;&#x6570;&#x3002;</strong></p>
<pre><code class="lang-python"><span class="hljs-comment"># -*- coding:utf-8 -*-</span>
<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">__init__</span><span class="hljs-params">(self)</span>:</span>
        self.arr=[]
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">Insert</span><span class="hljs-params">(self, num)</span>:</span>
        self.arr.append(num)
        self.arr.sort()
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">GetMedian</span><span class="hljs-params">(self,fuck)</span>:</span>
        length=len(self.arr)
        <span class="hljs-keyword">if</span> length%<span class="hljs-number">2</span>==<span class="hljs-number">1</span>:
            <span class="hljs-keyword">return</span> self.arr[length//<span class="hljs-number">2</span>]
        <span class="hljs-keyword">return</span>(self.arr[length//<span class="hljs-number">2</span>]+self.arr[length//<span class="hljs-number">2</span>-<span class="hljs-number">1</span>])/<span class="hljs-number">2.0</span>
</code></pre>
<pre><code class="lang-python"><span class="hljs-comment"># -*- coding:utf-8 -*-</span>
<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">__init__</span><span class="hljs-params">(self)</span>:</span>
        self.littleValueMaxHeap = []
        self.bigValueMinHeap = []
        self.maxHeapCount = <span class="hljs-number">0</span>
        self.minHeapCount = <span class="hljs-number">0</span>

    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">Insert</span><span class="hljs-params">(self, num)</span>:</span>
        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">cmpMaxHeap</span><span class="hljs-params">(a, b)</span>:</span>
            <span class="hljs-keyword">return</span> a &gt; b

        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">cmpMinHeap</span><span class="hljs-params">(a, b)</span>:</span>
            <span class="hljs-keyword">return</span> a &lt; b

        <span class="hljs-comment"># write code here</span>
        <span class="hljs-keyword">if</span> self.maxHeapCount &gt; self.minHeapCount:
            self.minHeapCount += <span class="hljs-number">1</span>
            <span class="hljs-keyword">if</span> num &lt; self.littleValueMaxHeap[<span class="hljs-number">0</span>]:
                tmpNum = self.littleValueMaxHeap[<span class="hljs-number">0</span>]
                self.adjustHeap(num, self.littleValueMaxHeap, cmpMaxHeap)
                self.createHeap(tmpNum, self.bigValueMinHeap, cmpMinHeap)
            <span class="hljs-keyword">else</span>:
                self.createHeap(num, self.bigValueMinHeap, cmpMinHeap)
        <span class="hljs-keyword">else</span>:
            self.maxHeapCount += <span class="hljs-number">1</span>
            <span class="hljs-keyword">if</span> len(self.littleValueMaxHeap) == <span class="hljs-number">0</span>:
                self.createHeap(num, self.littleValueMaxHeap, cmpMaxHeap)
            <span class="hljs-keyword">else</span>:
                <span class="hljs-keyword">if</span> self.bigValueMinHeap[<span class="hljs-number">0</span>] &lt; num:
                    tmpNum = self.bigValueMinHeap[<span class="hljs-number">0</span>]
                    self.adjustHeap(num, self.bigValueMinHeap, cmpMinHeap)
                    self.createHeap(tmpNum, self.littleValueMaxHeap, cmpMaxHeap)
                <span class="hljs-keyword">else</span>:
                    self.createHeap(num, self.littleValueMaxHeap, cmpMaxHeap)
        <span class="hljs-comment"># print(self.littleValueMaxHeap)</span>
        <span class="hljs-comment"># print(self.bigValueMinHeap)</span>

    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">GetMedian</span><span class="hljs-params">(self, n=None)</span>:</span>
        <span class="hljs-comment"># write code here</span>
        <span class="hljs-keyword">if</span> self.minHeapCount &lt; self.maxHeapCount:
            <span class="hljs-keyword">return</span> self.littleValueMaxHeap[<span class="hljs-number">0</span>]
        <span class="hljs-keyword">else</span>:
            <span class="hljs-keyword">return</span> float(self.littleValueMaxHeap[<span class="hljs-number">0</span>] + self.bigValueMinHeap[<span class="hljs-number">0</span>]) / <span class="hljs-number">2</span>

    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">createHeap</span><span class="hljs-params">(self, num, heap, cmpfun)</span>:</span>
        heap.append(num)
        tmpIndex = len(heap) - <span class="hljs-number">1</span>
        <span class="hljs-keyword">while</span> tmpIndex:
            parentIndex = (tmpIndex - <span class="hljs-number">1</span>) // <span class="hljs-number">2</span>
            <span class="hljs-keyword">if</span> cmpfun(heap[tmpIndex], heap[parentIndex]):
                heap[parentIndex], heap[tmpIndex] = \
                    heap[tmpIndex], heap[parentIndex]
                tmpIndex = parentIndex
            <span class="hljs-keyword">else</span>:
                <span class="hljs-keyword">break</span>

    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">adjustHeap</span><span class="hljs-params">(self, num, heap, cmpFunc)</span>:</span>
        <span class="hljs-keyword">if</span> num &lt; heap[<span class="hljs-number">0</span>]:
            maxHeapLen = len(heap)
            heap[<span class="hljs-number">0</span>] = num
            tmpIndex = <span class="hljs-number">0</span>
            <span class="hljs-keyword">while</span> tmpIndex &lt; maxHeapLen:
                leftIndex = tmpIndex * <span class="hljs-number">2</span> + <span class="hljs-number">1</span>
                rightIndex = tmpIndex * <span class="hljs-number">2</span> + <span class="hljs-number">2</span>
                largerIndex = <span class="hljs-number">0</span>
                <span class="hljs-keyword">if</span> rightIndex &lt; maxHeapLen:
                    largerIndex = rightIndex <span class="hljs-keyword">if</span> cmpFunc(heap[rightIndex], heap[leftIndex]) <span class="hljs-keyword">else</span> leftIndex
                <span class="hljs-keyword">elif</span> leftIndex &lt; maxHeapLen:
                    largerIndex = leftIndex
                <span class="hljs-keyword">else</span>:
                    <span class="hljs-keyword">break</span>

                <span class="hljs-keyword">if</span> cmpFunc(heap[largerIndex], heap[tmpIndex]):
                    heap[largerIndex], heap[tmpIndex] = \
                        heap[tmpIndex], heap[largerIndex]
                    index = largerIndex
                <span class="hljs-keyword">else</span>:
                    <span class="hljs-keyword">break</span>
</code></pre>
<h2 id="34&#x4E8C;&#x53C9;&#x6811;&#x7684;&#x4E0B;&#x4E00;&#x4E2A;&#x7ED3;&#x70B9;">34.&#x4E8C;&#x53C9;&#x6811;&#x7684;&#x4E0B;&#x4E00;&#x4E2A;&#x7ED3;&#x70B9;</h2>
<p><strong>&#x7ED9;&#x5B9A;&#x4E00;&#x4E2A;&#x4E8C;&#x53C9;&#x6811;&#x548C;&#x5176;&#x4E2D;&#x7684;&#x4E00;&#x4E2A;&#x7ED3;&#x70B9;&#xFF0C;&#x8BF7;&#x627E;&#x51FA;&#x4E2D;&#x5E8F;&#x904D;&#x5386;&#x987A;&#x5E8F;&#x7684;&#x4E0B;&#x4E00;&#x4E2A;&#x7ED3;&#x70B9;&#x5E76;&#x4E14;&#x8FD4;&#x56DE;&#x3002;&#x6CE8;&#x610F;&#xFF0C;&#x6811;&#x4E2D;&#x7684;&#x7ED3;&#x70B9;&#x4E0D;&#x4EC5;&#x5305;&#x542B;&#x5DE6;&#x53F3;&#x5B50;&#x7ED3;&#x70B9;&#xFF0C;&#x540C;&#x65F6;&#x5305;&#x542B;&#x6307;&#x5411;&#x7236;&#x7ED3;&#x70B9;&#x7684;&#x6307;&#x9488;&#x3002;</strong></p>
<pre><code class="lang-python"><span class="hljs-comment"># -*- coding:utf-8 -*-</span>
<span class="hljs-comment"># class TreeLinkNode:</span>
<span class="hljs-comment">#     def __init__(self, x):</span>
<span class="hljs-comment">#         self.val = x</span>
<span class="hljs-comment">#         self.left = None</span>
<span class="hljs-comment">#         self.right = None</span>
<span class="hljs-comment">#         self.next = None</span>
<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">GetNext</span><span class="hljs-params">(self, pNode)</span>:</span>
        <span class="hljs-comment"># write code her</span>
        <span class="hljs-comment">#&#x5BFB;&#x627E;&#x53F3;&#x5B50;&#x6811;&#xFF0C;&#x5982;&#x679C;&#x5B58;&#x5728;&#x5C31;&#x4E00;&#x76F4;&#x627E;&#x5230;&#x53F3;&#x5B50;&#x6811;&#x7684;&#x6700;&#x5DE6;&#x8FB9;&#x5C31;&#x662F;&#x4E0B;&#x4E00;&#x4E2A;&#x8282;&#x70B9;</span>
        <span class="hljs-comment"># &#x6CA1;&#x6709;&#x53F3;&#x5B50;&#x6811;&#xFF0C;&#x5C31;&#x5BFB;&#x627E;&#x4ED6;&#x7684;&#x7236;&#x8282;&#x70B9;&#xFF0C;&#x4E00;&#x76F4;&#x627E;&#x5230;&#x5B83;&#x662F;&#x7236;&#x8282;&#x70B9;&#x7684;&#x5DE6;&#x5B50;&#x6811;&#xFF0C;&#x6253;&#x5370;&#x7236;&#x8282;&#x70B9;</span>
        <span class="hljs-keyword">if</span> pNode.right:
            tmpNode = pNode.right
            <span class="hljs-keyword">while</span> tmpNode.left:
                tmpNode = tmpNode.left
            <span class="hljs-keyword">return</span> tmpNode
        <span class="hljs-keyword">else</span>:
            tmpNode =pNode
            <span class="hljs-keyword">while</span> tmpNode.next:
                <span class="hljs-keyword">if</span> tmpNode.next.left == tmpNode:
                    <span class="hljs-keyword">return</span> tmpNode.next
                tmpNode = tmpNode.next
            <span class="hljs-keyword">return</span> <span class="hljs-keyword">None</span>
</code></pre>
<h2 id="35&#x5BF9;&#x79F0;&#x7684;&#x4E8C;&#x53C9;&#x6811;">35.&#x5BF9;&#x79F0;&#x7684;&#x4E8C;&#x53C9;&#x6811;</h2>
<p><strong>&#x8BF7;&#x5B9E;&#x73B0;&#x4E00;&#x4E2A;&#x51FD;&#x6570;&#xFF0C;&#x7528;&#x6765;&#x5224;&#x65AD;&#x4E00;&#x9897;&#x4E8C;&#x53C9;&#x6811;&#x662F;&#x4E0D;&#x662F;&#x5BF9;&#x79F0;&#x7684;&#x3002;&#x6CE8;&#x610F;&#xFF0C;&#x5982;&#x679C;&#x4E00;&#x4E2A;&#x4E8C;&#x53C9;&#x6811;&#x540C;&#x6B64;&#x4E8C;&#x53C9;&#x6811;&#x7684;&#x955C;&#x50CF;&#x662F;&#x540C;&#x6837;&#x7684;&#xFF0C;&#x5B9A;&#x4E49;&#x5176;&#x4E3A;&#x5BF9;&#x79F0;&#x7684;&#x3002;</strong></p>
<pre><code class="lang-python"><span class="hljs-comment"># -*- coding:utf-8 -*-</span>
<span class="hljs-comment"># class TreeNode:</span>
<span class="hljs-comment">#     def __init__(self, x):</span>
<span class="hljs-comment">#         self.val = x</span>
<span class="hljs-comment">#         self.left = None</span>
<span class="hljs-comment">#         self.right = None</span>
<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">isSymmetrical</span><span class="hljs-params">(self, pRoot)</span>:</span>
        <span class="hljs-comment"># write code here</span>
        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">isMirror</span><span class="hljs-params">(left, right)</span>:</span>
            <span class="hljs-keyword">if</span> left == <span class="hljs-keyword">None</span> <span class="hljs-keyword">and</span> right == <span class="hljs-keyword">None</span>:
                <span class="hljs-keyword">return</span> <span class="hljs-keyword">True</span>
            <span class="hljs-keyword">elif</span> left == <span class="hljs-keyword">None</span> <span class="hljs-keyword">or</span> right == <span class="hljs-keyword">None</span>:
                <span class="hljs-keyword">return</span> <span class="hljs-keyword">False</span>

            <span class="hljs-keyword">if</span> left.val != right.val:
                <span class="hljs-keyword">return</span>
</code></pre>
<h2 id="36&#x6309;&#x4E4B;&#x5B57;&#x5F62;&#x987A;&#x5E8F;&#x6253;&#x5370;&#x4E8C;&#x53C9;&#x6811;">36.&#x6309;&#x4E4B;&#x5B57;&#x5F62;&#x987A;&#x5E8F;&#x6253;&#x5370;&#x4E8C;&#x53C9;&#x6811;</h2>
<p><strong>&#x8BF7;&#x5B9E;&#x73B0;&#x4E00;&#x4E2A;&#x51FD;&#x6570;&#x6309;&#x7167;&#x4E4B;&#x5B57;&#x5F62;&#x6253;&#x5370;&#x4E8C;&#x53C9;&#x6811;&#xFF0C;&#x5373;&#x7B2C;&#x4E00;&#x884C;&#x6309;&#x7167;&#x4ECE;&#x5DE6;&#x5230;&#x53F3;&#x7684;&#x987A;&#x5E8F;&#x6253;&#x5370;&#xFF0C;&#x7B2C;&#x4E8C;&#x5C42;&#x6309;&#x7167;&#x4ECE;&#x53F3;&#x81F3;&#x5DE6;&#x7684;&#x987A;&#x5E8F;&#x6253;&#x5370;&#xFF0C;&#x7B2C;&#x4E09;&#x884C;&#x6309;&#x7167;&#x4ECE;&#x5DE6;&#x5230;&#x53F3;&#x7684;&#x987A;&#x5E8F;&#x6253;&#x5370;&#xFF0C;&#x5176;&#x4ED6;&#x884C;&#x4EE5;&#x6B64;&#x7C7B;&#x63A8;&#x3002;</strong></p>
<pre><code class="lang-python"><span class="hljs-comment"># -*- coding:utf-8 -*-</span>
<span class="hljs-comment"># class TreeNode:</span>
<span class="hljs-comment">#     def __init__(self, x):</span>
<span class="hljs-comment">#         self.val = x</span>
<span class="hljs-comment">#         self.left = None</span>
<span class="hljs-comment">#         self.right = None</span>
<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">Print</span><span class="hljs-params">(self, pRoot)</span>:</span>
        <span class="hljs-comment"># write code here</span>
        <span class="hljs-keyword">if</span> pRoot == <span class="hljs-keyword">None</span>:
            <span class="hljs-keyword">return</span> []

        stack1 = [pRoot]
        stack2 = []

        ret = []
        <span class="hljs-keyword">while</span> stack1 <span class="hljs-keyword">or</span> stack2:
            <span class="hljs-keyword">if</span> stack1:
                tmpRet = []
                <span class="hljs-keyword">while</span> stack1:
                    tmpNode = stack1.pop()
                    tmpRet.append(tmpNode.val)
                    <span class="hljs-keyword">if</span> tmpNode.left:
                        stack2.append(tmpNode.left)
                    <span class="hljs-keyword">if</span> tmpNode.right:
                        stack2.append(tmpNode.right)
                ret.append(tmpRet)

            <span class="hljs-keyword">if</span> stack2:
                tmpRet = []
                <span class="hljs-keyword">while</span> stack2:
                    tmpNode = stack2.pop()
                    tmpRet.append(tmpNode.val)
                    <span class="hljs-keyword">if</span> tmpNode.right:
                        stack1.append(tmpNode.right)
                    <span class="hljs-keyword">if</span> tmpNode.left:
                        stack1.append(tmpNode.left)

                ret.append(tmpRet)
        <span class="hljs-keyword">return</span> ret
</code></pre>
<h2 id="37&#x628A;&#x4E8C;&#x53C9;&#x6811;&#x6253;&#x5370;&#x6210;&#x591A;&#x884C;">37.&#x628A;&#x4E8C;&#x53C9;&#x6811;&#x6253;&#x5370;&#x6210;&#x591A;&#x884C;</h2>
<p><strong>&#x4ECE;&#x4E0A;&#x5230;&#x4E0B;&#x6309;&#x5C42;&#x6253;&#x5370;&#x4E8C;&#x53C9;&#x6811;&#xFF0C;&#x540C;&#x4E00;&#x5C42;&#x7ED3;&#x70B9;&#x4ECE;&#x5DE6;&#x81F3;&#x53F3;&#x8F93;&#x51FA;&#x3002;&#x6BCF;&#x4E00;&#x5C42;&#x8F93;&#x51FA;&#x4E00;&#x884C;&#x3002;</strong></p>
<pre><code class="lang-python"><span class="hljs-comment"># -*- coding:utf-8 -*-</span>
<span class="hljs-comment"># class TreeNode:</span>
<span class="hljs-comment">#     def __init__(self, x):</span>
<span class="hljs-comment">#         self.val = x</span>
<span class="hljs-comment">#         self.left = None</span>
<span class="hljs-comment">#         self.right = None</span>
<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-comment"># &#x8FD4;&#x56DE;&#x4E8C;&#x7EF4;&#x5217;&#x8868;[[1,2],[4,5]]</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">Print</span><span class="hljs-params">(self, pRoot)</span>:</span>
        <span class="hljs-comment"># write code here</span>
        <span class="hljs-keyword">if</span> pRoot == <span class="hljs-keyword">None</span>:
            <span class="hljs-keyword">return</span> []
        queue1 = [pRoot]
        queue2 = []
        ret = []
        <span class="hljs-keyword">while</span> queue1 <span class="hljs-keyword">or</span> queue2:
            <span class="hljs-keyword">if</span> queue1:
                tmpRet = []
                <span class="hljs-keyword">while</span> queue1:
                    tmpNode = queue1[<span class="hljs-number">0</span>]
                    tmpRet.append(tmpNode.val)
                    <span class="hljs-keyword">del</span> queue1[<span class="hljs-number">0</span>]
                    <span class="hljs-keyword">if</span> tmpNode.left:
                        queue2.append(tmpNode.left)
                    <span class="hljs-keyword">if</span> tmpNode.right:
                        queue2.append(tmpNode.right)
                ret.append(tmpRet)
            <span class="hljs-keyword">if</span> queue2:
                tmpRet = []
                <span class="hljs-keyword">while</span> queue2:
                    tmpNode = queue2[<span class="hljs-number">0</span>]
                    tmpRet.append(tmpNode.val)
                    <span class="hljs-keyword">del</span> queue2[<span class="hljs-number">0</span>]
                    <span class="hljs-keyword">if</span> tmpNode.left:
                        queue1.append(tmpNode.left)
                    <span class="hljs-keyword">if</span> tmpNode.right:
                        queue1.append(tmpNode.right)
                ret.append(tmpRet)
        <span class="hljs-keyword">return</span> ret
</code></pre>
<h2 id="38&#x4E8C;&#x53C9;&#x641C;&#x7D22;&#x6811;&#x7684;&#x7B2C;k&#x4E2A;&#x7ED3;&#x70B9;">38.&#x4E8C;&#x53C9;&#x641C;&#x7D22;&#x6811;&#x7684;&#x7B2C;k&#x4E2A;&#x7ED3;&#x70B9;</h2>
<p><strong>&#x7ED9;&#x5B9A;&#x4E00;&#x68F5;&#x4E8C;&#x53C9;&#x641C;&#x7D22;&#x6811;&#xFF0C;&#x8BF7;&#x627E;&#x51FA;&#x5176;&#x4E2D;&#x7684;&#x7B2C;k&#x5C0F;&#x7684;&#x7ED3;&#x70B9;&#x3002;&#x4F8B;&#x5982;&#xFF0C; &#xFF08;5&#xFF0C;3&#xFF0C;7&#xFF0C;2&#xFF0C;4&#xFF0C;6&#xFF0C;8&#xFF09;    &#x4E2D;&#xFF0C;&#x6309;&#x7ED3;&#x70B9;&#x6570;&#x503C;&#x5927;&#x5C0F;&#x987A;&#x5E8F;&#x7B2C;&#x4E09;&#x5C0F;&#x7ED3;&#x70B9;&#x7684;&#x503C;&#x4E3A;4&#x3002;</strong></p>
<pre><code class="lang-python"><span class="hljs-comment"># -*- coding:utf-8 -*-</span>
<span class="hljs-comment"># class TreeNode:</span>
<span class="hljs-comment">#     def __init__(self, x):</span>
<span class="hljs-comment">#         self.val = x</span>
<span class="hljs-comment">#         self.left = None</span>
<span class="hljs-comment">#         self.right = None</span>
<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-comment"># &#x8FD4;&#x56DE;&#x5BF9;&#x5E94;&#x8282;&#x70B9;TreeNode</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">KthNode</span><span class="hljs-params">(self, pRoot, k)</span>:</span>
        <span class="hljs-comment"># write code here</span>
        retList = []

        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">preOrder</span><span class="hljs-params">(pRoot)</span>:</span>
            <span class="hljs-keyword">if</span> pRoot == <span class="hljs-keyword">None</span>:
                <span class="hljs-keyword">return</span> <span class="hljs-keyword">None</span>
            preOrder(pRoot.left)
            retList.append(pRoot)
            preOrder(pRoot.right)

        preOrder(pRoot)
        <span class="hljs-keyword">if</span> len(retList) &lt; k <span class="hljs-keyword">or</span> k &lt; <span class="hljs-number">1</span>:
            <span class="hljs-keyword">return</span> <span class="hljs-keyword">None</span>

        <span class="hljs-keyword">return</span> retList[k - <span class="hljs-number">1</span>]
</code></pre>
<h2 id="39&#x5E8F;&#x5217;&#x5316;&#x4E8C;&#x53C9;&#x6811;">39.&#x5E8F;&#x5217;&#x5316;&#x4E8C;&#x53C9;&#x6811;</h2>
<p><strong>&#x8BF7;&#x5B9E;&#x73B0;&#x4E24;&#x4E2A;&#x51FD;&#x6570;&#xFF0C;&#x5206;&#x522B;&#x7528;&#x6765;&#x5E8F;&#x5217;&#x5316;&#x548C;&#x53CD;&#x5E8F;&#x5217;&#x5316;&#x4E8C;&#x53C9;&#x6811;</strong></p>
<pre><code class="lang-python"><span class="hljs-comment"># -*- coding:utf-8 -*-</span>
<span class="hljs-comment"># class TreeNode:</span>
<span class="hljs-comment">#     def __init__(self, x):</span>
<span class="hljs-comment">#         self.val = x</span>
<span class="hljs-comment">#         self.left = None</span>
<span class="hljs-comment">#         self.right = None</span>
<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">Serialize</span><span class="hljs-params">(self, root)</span>:</span>
        <span class="hljs-comment"># write code here</span>
        retList = []

        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">preOrder</span><span class="hljs-params">(root)</span>:</span>
            <span class="hljs-keyword">if</span> root == <span class="hljs-keyword">None</span>:
                retList.append(<span class="hljs-string">&apos;#&apos;</span>)
                <span class="hljs-keyword">return</span>
            retList.append(str(root.val))
            preOrder(root.left)
            preOrder(root.right)

        preOrder(root)
        <span class="hljs-keyword">return</span> <span class="hljs-string">&apos; &apos;</span>.join(retList)

    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">Deserialize</span><span class="hljs-params">(self, s)</span>:</span>
        <span class="hljs-comment"># write code here</span>
        retList = s.split()

        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">dePreOrder</span><span class="hljs-params">()</span>:</span>
            <span class="hljs-keyword">if</span> retList == []:
                <span class="hljs-keyword">return</span> <span class="hljs-keyword">None</span>
            rootVal = retList[<span class="hljs-number">0</span>]
            <span class="hljs-keyword">del</span> retList[<span class="hljs-number">0</span>]
            <span class="hljs-keyword">if</span> rootVal == <span class="hljs-string">&apos;#&apos;</span>:
                <span class="hljs-keyword">return</span> <span class="hljs-keyword">None</span>
            node = TreeNode(int(rootVal))

            leftNode = dePreOrder()
            rightNode = dePreOrder()

            node.left = leftNode
            node.right = rightNode
            <span class="hljs-keyword">return</span> node

        pRoot = dePreOrder()
        <span class="hljs-keyword">return</span> pRoot
</code></pre>
<h2 id="40&#x8FDE;&#x7EED;&#x5B50;&#x6570;&#x7EC4;&#x7684;&#x6700;&#x5927;&#x548C;">40.&#x8FDE;&#x7EED;&#x5B50;&#x6570;&#x7EC4;&#x7684;&#x6700;&#x5927;&#x548C;</h2>
<p><strong>HZ&#x5076;&#x5C14;&#x4F1A;&#x62FF;&#x4E9B;&#x4E13;&#x4E1A;&#x95EE;&#x9898;&#x6765;&#x5FFD;&#x60A0;&#x90A3;&#x4E9B;&#x975E;&#x8BA1;&#x7B97;&#x673A;&#x4E13;&#x4E1A;&#x7684;&#x540C;&#x5B66;&#x3002;&#x4ECA;&#x5929;&#x6D4B;&#x8BD5;&#x7EC4;&#x5F00;&#x5B8C;&#x4F1A;&#x540E;,&#x4ED6;&#x53C8;&#x53D1;&#x8BDD;&#x4E86;:&#x5728;&#x53E4;&#x8001;&#x7684;&#x4E00;&#x7EF4;&#x6A21;&#x5F0F;&#x8BC6;&#x522B;&#x4E2D;,&#x5E38;&#x5E38;&#x9700;&#x8981;&#x8BA1;&#x7B97;&#x8FDE;&#x7EED;&#x5B50;&#x5411;&#x91CF;&#x7684;&#x6700;&#x5927;&#x548C;,&#x5F53;&#x5411;&#x91CF;&#x5168;&#x4E3A;&#x6B63;&#x6570;&#x7684;&#x65F6;&#x5019;,&#x95EE;&#x9898;&#x5F88;&#x597D;&#x89E3;&#x51B3;&#x3002;&#x4F46;&#x662F;,&#x5982;&#x679C;&#x5411;&#x91CF;&#x4E2D;&#x5305;&#x542B;&#x8D1F;&#x6570;,&#x662F;&#x5426;&#x5E94;&#x8BE5;&#x5305;&#x542B;&#x67D0;&#x4E2A;&#x8D1F;&#x6570;,&#x5E76;&#x671F;&#x671B;&#x65C1;&#x8FB9;&#x7684;&#x6B63;&#x6570;&#x4F1A;&#x5F25;&#x8865;&#x5B83;&#x5462;&#xFF1F;&#x4F8B;&#x5982;:{6,-3,-2,7,-15,1,2,2},&#x8FDE;&#x7EED;&#x5B50;&#x5411;&#x91CF;&#x7684;&#x6700;&#x5927;&#x548C;&#x4E3A;8(&#x4ECE;&#x7B2C;0&#x4E2A;&#x5F00;&#x59CB;,&#x5230;&#x7B2C;3&#x4E2A;&#x4E3A;&#x6B62;)&#x3002;&#x7ED9;&#x4E00;&#x4E2A;&#x6570;&#x7EC4;&#xFF0C;&#x8FD4;&#x56DE;&#x5B83;&#x7684;&#x6700;&#x5927;&#x8FDE;&#x7EED;&#x5B50;&#x5E8F;&#x5217;&#x7684;&#x548C;&#xFF0C;&#x4F60;&#x4F1A;&#x4E0D;&#x4F1A;&#x88AB;&#x4ED6;&#x5FFD;&#x60A0;&#x4F4F;&#xFF1F;(&#x5B50;&#x5411;&#x91CF;&#x7684;&#x957F;&#x5EA6;&#x81F3;&#x5C11;&#x662F;1)</strong></p>
<pre><code class="lang-python"><span class="hljs-comment"># -*- coding:utf-8 -*-</span>
<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">FindGreatestSumOfSubArray</span><span class="hljs-params">(self, array)</span>:</span>
        <span class="hljs-comment"># write code here</span>
        maxNum = <span class="hljs-keyword">None</span>
        tmpNum = <span class="hljs-number">0</span>

        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> array:
            <span class="hljs-keyword">if</span> maxNum == <span class="hljs-keyword">None</span>:
                maxNum = i
            <span class="hljs-keyword">if</span> tmpNum + i &lt; i:
                tmpNum = i
            <span class="hljs-keyword">else</span>:
                tmpNum += i
            <span class="hljs-keyword">if</span> maxNum &lt; tmpNum:
                maxNum = tmpNum
        <span class="hljs-keyword">return</span> maxNum
</code></pre>
<h2 id="41&#x77E9;&#x5F62;&#x7684;&#x8986;&#x76D6;">41.&#x77E9;&#x5F62;&#x7684;&#x8986;&#x76D6;</h2>
<p><strong>&#x6211;&#x4EEC;&#x53EF;&#x4EE5;&#x7528;2<em>1&#x7684;&#x5C0F;&#x77E9;&#x5F62;&#x6A2A;&#x7740;&#x6216;&#x8005;&#x7AD6;&#x7740;&#x53BB;&#x8986;&#x76D6;&#x66F4;&#x5927;&#x7684;&#x77E9;&#x5F62;&#x3002;&#x8BF7;&#x95EE;&#x7528;n&#x4E2A;2</em>1&#x7684;&#x5C0F;&#x77E9;&#x5F62;&#x65E0;&#x91CD;&#x53E0;&#x5730;&#x8986;&#x76D6;&#x4E00;&#x4E2A;2*n&#x7684;&#x5927;&#x77E9;&#x5F62;&#xFF0C;&#x603B;&#x5171;&#x6709;&#x591A;&#x5C11;&#x79CD;&#x65B9;&#x6CD5;&#xFF1F;</strong></p>
<pre><code class="lang-python"><span class="hljs-comment"># -*- coding:utf-8 -*-</span>
<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">rectCover</span><span class="hljs-params">(self, number)</span>:</span>
        <span class="hljs-comment"># write code here</span>
        <span class="hljs-comment">#if number == 0:</span>
            <span class="hljs-comment">#return 0</span>
        <span class="hljs-comment">#if number == 1:</span>
            <span class="hljs-comment">#return 1</span>
        <span class="hljs-comment">#if number == 2:</span>
            <span class="hljs-comment">#return 2</span>
        <span class="hljs-comment">#a = 1</span>
        <span class="hljs-comment">#b = 2</span>
        <span class="hljs-comment">#ret = 0</span>
        <span class="hljs-comment">#for  i in range(3,number+1):</span>
            <span class="hljs-comment">#ret = a + b</span>
            <span class="hljs-comment">#a = b</span>
            <span class="hljs-comment">#b = ret</span>
        <span class="hljs-comment">#return ret</span>
        res = [<span class="hljs-number">0</span>,<span class="hljs-number">1</span>,<span class="hljs-number">2</span>]
        <span class="hljs-keyword">while</span> len(res) &lt;= number:
            res.append(res[-<span class="hljs-number">2</span>]+res[-<span class="hljs-number">1</span>])
        <span class="hljs-keyword">return</span> res[number]
</code></pre>
<h2 id="42&#x5B57;&#x7B26;&#x4E32;&#x7684;&#x6392;&#x5217;">42.&#x5B57;&#x7B26;&#x4E32;&#x7684;&#x6392;&#x5217;</h2>
<p><strong>&#x8F93;&#x5165;&#x4E00;&#x4E2A;&#x5B57;&#x7B26;&#x4E32;,&#x6309;&#x5B57;&#x5178;&#x5E8F;&#x6253;&#x5370;&#x51FA;&#x8BE5;&#x5B57;&#x7B26;&#x4E32;&#x4E2D;&#x5B57;&#x7B26;&#x7684;&#x6240;&#x6709;&#x6392;&#x5217;&#x3002;&#x4F8B;&#x5982;&#x8F93;&#x5165;&#x5B57;&#x7B26;&#x4E32;abc,&#x5219;&#x6253;&#x5370;&#x51FA;&#x7531;&#x5B57;&#x7B26;a,b,c&#x6240;&#x80FD;&#x6392;&#x5217;&#x51FA;&#x6765;&#x7684;&#x6240;&#x6709;&#x5B57;&#x7B26;&#x4E32;abc,acb,bac,bca,cab&#x548C;cba&#x3002;</strong></p>
<h5 id="&#x8F93;&#x5165;&#x63CF;&#x8FF0;">&#x8F93;&#x5165;&#x63CF;&#x8FF0;:</h5>
<pre><code class="lang-python">&#x8F93;&#x5165;&#x4E00;&#x4E2A;&#x5B57;&#x7B26;&#x4E32;,&#x957F;&#x5EA6;&#x4E0D;&#x8D85;&#x8FC7;<span class="hljs-number">9</span>(&#x53EF;&#x80FD;&#x6709;&#x5B57;&#x7B26;&#x91CD;&#x590D;),&#x5B57;&#x7B26;&#x53EA;&#x5305;&#x62EC;&#x5927;&#x5C0F;&#x5199;&#x5B57;&#x6BCD;&#x3002;
</code></pre>
<pre><code class="lang-python"><span class="hljs-comment"># -*- coding:utf-8 -*-</span>
<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">Permutation</span><span class="hljs-params">(self, ss)</span>:</span>
        <span class="hljs-comment"># write code here</span>
        <span class="hljs-keyword">import</span> itertools
        result = []
        <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> ss:
            <span class="hljs-keyword">return</span> []
        <span class="hljs-keyword">else</span>:
            res = itertools.permutations(ss)
            <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> res:
                <span class="hljs-keyword">if</span> <span class="hljs-string">&quot;&quot;</span>.join(i) <span class="hljs-keyword">not</span> <span class="hljs-keyword">in</span> result:
                    result.append(<span class="hljs-string">&quot;&quot;</span>.join(i))
        <span class="hljs-keyword">return</span> result
</code></pre>
<h2 id="43&#x628A;&#x6570;&#x7EC4;&#x6392;&#x6210;&#x6700;&#x5C0F;&#x7684;&#x6570;">43.&#x628A;&#x6570;&#x7EC4;&#x6392;&#x6210;&#x6700;&#x5C0F;&#x7684;&#x6570;</h2>
<p><strong>&#x8F93;&#x5165;&#x4E00;&#x4E2A;&#x6B63;&#x6574;&#x6570;&#x6570;&#x7EC4;&#xFF0C;&#x628A;&#x6570;&#x7EC4;&#x91CC;&#x6240;&#x6709;&#x6570;&#x5B57;&#x62FC;&#x63A5;&#x8D77;&#x6765;&#x6392;&#x6210;&#x4E00;&#x4E2A;&#x6570;&#xFF0C;&#x6253;&#x5370;&#x80FD;&#x62FC;&#x63A5;&#x51FA;&#x7684;&#x6240;&#x6709;&#x6570;&#x5B57;&#x4E2D;&#x6700;&#x5C0F;&#x7684;&#x4E00;&#x4E2A;&#x3002;&#x4F8B;&#x5982;&#x8F93;&#x5165;&#x6570;&#x7EC4;{3&#xFF0C;32&#xFF0C;321}&#xFF0C;&#x5219;&#x6253;&#x5370;&#x51FA;&#x8FD9;&#x4E09;&#x4E2A;&#x6570;&#x5B57;&#x80FD;&#x6392;&#x6210;&#x7684;&#x6700;&#x5C0F;&#x6570;&#x5B57;&#x4E3A;321323&#x3002;</strong></p>
<pre><code class="lang-python"><span class="hljs-comment"># -*- coding:utf-8 -*-</span>
<span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">QuickSort</span><span class="hljs-params">(array,left=<span class="hljs-number">0</span>,right=None,cmp=None)</span>:</span>
    arrayLen = len(array)
    <span class="hljs-keyword">if</span> arrayLen &lt;= <span class="hljs-number">1</span>:
        <span class="hljs-keyword">return</span>
    <span class="hljs-keyword">if</span> right == <span class="hljs-keyword">None</span>:
        right = arrayLen -<span class="hljs-number">1</span>
    <span class="hljs-keyword">if</span> left &lt; right:
        pivot = partition(array,left,right,cmp)
        QuickSort(array,left,pivot-<span class="hljs-number">1</span>,cmp)
        QuickSort(array,pivot+<span class="hljs-number">1</span>,right,cmp)

<span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">partition</span><span class="hljs-params">(array,left,right,cmp=None)</span>:</span>
    i = left-<span class="hljs-number">1</span>
    <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(left,right):
        smaller = <span class="hljs-keyword">False</span>
        <span class="hljs-keyword">if</span> cmp:
            smaller = cmp(array[j],array[right])
        <span class="hljs-keyword">elif</span> array[j] &lt; array[right]:
            smaller = <span class="hljs-keyword">True</span>
        <span class="hljs-keyword">if</span> smaller:
            array[j],array[i+<span class="hljs-number">1</span>] = array[i+<span class="hljs-number">1</span>],array[j]
            i += <span class="hljs-number">1</span>
    array[right],array[i+<span class="hljs-number">1</span>] = array[i+<span class="hljs-number">1</span>],array[right]
    <span class="hljs-keyword">return</span> i+<span class="hljs-number">1</span>

<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">PrintMinNumber</span><span class="hljs-params">(self, numbers)</span>:</span>
        <span class="hljs-comment"># write code here</span>
        <span class="hljs-comment"># def cmpNum(num1,num2):</span>
        <span class="hljs-comment">#     n1 = str(num1) + str(num2)</span>
        <span class="hljs-comment">#     n2 = str(num2) + str(num1)</span>
        <span class="hljs-comment">#     if int(n1) &lt; int(n2):</span>
        <span class="hljs-comment">#         return True</span>
        <span class="hljs-comment">#     else:</span>
        <span class="hljs-comment">#         return False</span>
        QuickSort(numbers,cmp=<span class="hljs-keyword">lambda</span> num1,num2: <span class="hljs-number">1</span> <span class="hljs-keyword">if</span> str(num1)+str(num2) &lt; str(num2)+str(num1) <span class="hljs-keyword">else</span> <span class="hljs-number">0</span> )
        <span class="hljs-comment"># numbers.sort(key=cmpNum)</span>
        <span class="hljs-comment"># ret = &apos;&apos;</span>
        <span class="hljs-comment"># for i in numbers:</span>
        <span class="hljs-comment">#     ret += str(i)</span>

        <span class="hljs-keyword">return</span> <span class="hljs-string">&apos;&apos;</span>.join(map(str,numbers))


<span class="hljs-keyword">if</span> __name__ == <span class="hljs-string">&apos;__main__&apos;</span>:
    s = Solution()
    res = s.PrintMinNumber([<span class="hljs-number">3</span>,<span class="hljs-number">32</span>,<span class="hljs-number">321</span>,<span class="hljs-number">45</span>])
    print(res)
</code></pre>

                    
                    </section>
                
                
                </div>
            </div>
        </div>

        
        <a href="../剑指offer/剑指offer1-24题.html" class="navigation navigation-prev " aria-label="Previous page: 剑指offer1-24题"><i class="fa fa-angle-left"></i></a>
        
        
        <a href="../树的实现/树的定义.html" class="navigation navigation-next " aria-label="Next page: 各种树"><i class="fa fa-angle-right"></i></a>
        
    </div>
</div>

        
<script src="../gitbook/app.js"></script>

    
    <script src="../gitbook/plugins/gitbook-plugin-search/lunr.min.js"></script>
    

    
    <script src="../gitbook/plugins/gitbook-plugin-search/search.js"></script>
    

    
    <script src="../gitbook/plugins/gitbook-plugin-sharing/buttons.js"></script>
    

    
    <script src="../gitbook/plugins/gitbook-plugin-fontsettings/buttons.js"></script>
    

<script>
require(["gitbook"], function(gitbook) {
    var config = {"highlight":{},"search":{"maxIndexSize":1000000},"sharing":{"facebook":true,"twitter":true,"google":false,"weibo":false,"instapaper":false,"vk":false,"all":["facebook","google","twitter","weibo","instapaper"]},"fontsettings":{"theme":"white","family":"sans","size":2}};
    gitbook.start(config);
});
</script>

        
    </body>
    
</html>
